Computational experiments on graph width metrics

Abstract

Many real-life problems can be modelled using graphs. However, the solutions to these problems are often NP-complete. In 1986, Robertson and Seymour introduced the notion of a tree-decomposition of a graph, with an associated width called the treewidth, as a formal characterisation of how "tree-like" a graph is. Subsequently, Arnborg and Proskurowski developed techniques for using tree-decompositions to construct dynamic programming algorithms for solving problems such as DOMINATING SET, VERTEX COVER and INDEPENDENT SET. Unfortunately, the problem of finding a minimum width tree decomposition for a graph is NP-complete in general. Moreover, such dynamic programming algorithms are exponential in w, the width of the decomposition. As such, there is an interest in developing heuristics to estimate a graph's treewidth. But for any such heuristic to be useful, it must be on the one hand efficient, and on the other hand accurate. In this thesis, we discuss upper bound heuristics for general graphs based on graph triangulations and on vertex separators. We also discuss a treewidth lower bound based on the theory of online graphs. We then experimentally investigate the running time and accuracy of the algorithms on two classes of random graph. This work grew out of a paper by Koster, Bodlaender and van Hoesel ([43]), and some of these results will be published in an updated version of this paper.