Theory and Practical Applications of Treewidth

Abstract

This thesis studies the theory and practical applications of separator-based dynamic programming (and in particular treewidth) for solving combinatorial problems in graphs. The thesis consists of three parts; the first focusing on graph embedding problems, the second on problems in geometric intersection graphs, and the third explores practical applications of these techniques to, among others, computing game-theoretic centrality measures. In the first part, we study graph embedding problems: given a graph, we want to determine whether it can be embedded into another graph, for instance as a subgraph or minor. We show that several such problems can be solved in time 2^O(n / log n) on n-vertex planar graphs and that, assuming the Exponential Time Hypothesis, this running time is optimal (i.e., there is no 2^o(n / log n)-time algorithm). These results are surprising, since many (hard) problems can be solved in time 2^O(sqrt n) in planar graphs using treewidth-based techniques; graph embedding problems seem to be an exception to this rule. The second part studies problems in geometric intersection graphs. A geometric intersection graph is obtained by taking a collection of objects in d-dimensional space (for instance, unit disks in 2D), and building a graph by taking a vertex corresponding to each object, with edges between each pair of vertices whose corresponding objects intersect. We show that many classical problems (such as independent set, dominating set and Steiner tree) can be solved in time 2^O(n^{1-1/d}), and this result is tight under the Exponential Time Hypothesis. To obtain these results, we introduce the notion of weighted clique-partitioned tree decompositions. While geometric intersection graphs can have unbounded treewidth, we show that they (under certain conditions) admit clique-partitioned tree decompositions of small width – and that this fact can be exploited to obtain fast algorithms. The third part explores practical applications of treewidth. As having a suitable tree decomposition is crucial for any such applied use, we first explore how the power of graphics processing units (GPUs) can be used to compute treewidth in parallel. We then study how treewidth can be exploited to compute game-theoretic centrality measures based on the Shapley value in graphs, and show that this can be applied to analyzing terrorist networks to identify the key entities.