Skip to Main content Skip to Navigation
Conference papers

An Experimental Study of the Treewidth of Real-World Graph Data

Silviu Maniu 1 Pierre Senellart 2, 3 Suraj Jog 4
2 VALDA - Value from Data
DI-ENS - Département d'informatique de l'École normale supérieure, Inria de Paris
3 DIG - Data, Intelligence and Graphs
LTCI - Laboratoire Traitement et Communication de l'Information
Abstract : Treewidth is a parameter that measures how tree-like a relational instance is, and whether it can reasonably be decomposed into a tree. Many computation tasks are known to be tractable on databases of small treewidth, but computing the treewidth of a given instance is intractable. This article is the first large-scale experimental study of treewidth and tree decompositions of real-world database instances (25 datasets from 8 different domains, with sizes ranging from a few thousand to a few million vertices). The goal is to determine which data, if any, can benefit of the wealth of algorithms for databases of small treewidth. For each dataset, we obtain upper and lower bound estimations of their treewidth, and study the properties of their tree decompositions. We show in particular that, even when treewidth is high, using partial tree decompositions can result in data structures that can assist algorithms.
Document type :
Conference papers
Complete list of metadatas

Cited literature [64 references]  Display  Hide  Download
Contributor : Pierre Senellart <>
Submitted on : Tuesday, April 2, 2019 - 12:41:47 PM
Last modification on : Monday, October 12, 2020 - 11:18:08 PM
Long-term archiving on: : Wednesday, July 3, 2019 - 3:16:34 PM


Files produced by the author(s)



Silviu Maniu, Pierre Senellart, Suraj Jog. An Experimental Study of the Treewidth of Real-World Graph Data. ICDT 2019 – 22nd International Conference on Database Theory, Mar 2019, Lisbon, Portugal. pp.18, ⟨10.4230/LIPIcs.ICDT.2019.12⟩. ⟨hal-02087763⟩



Record views


Files downloads