Title: An Experimental Study of the Treewidth of Real-World Graph Data (Extended Version),
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.