Silviu Maniu, Université Paris-Sud
7 February 2020, 10:30-11:30
ENS, S16
An Experimental Study of the Treewidth of Real-World Data
Treewidth is a parameter that measures how tree-like a data instance is, and whether it can reasonably be decomposed into a data structure resembling a tree.
Many computation tasks are known to be tractable on data having small treewidth, but computing the treewidth of a given instance is intractable. This talk presents the first large-scale experimental study of treewidth and tree decompositions of real-world data, with a focus on graph data. We aim to find out which data, if any, can benefit of the wealth of algorithms for data 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.
