Treewidth: Computational Experiments
Please always quote using this URN: urn:nbn:de:0297-zib-6644
- Many {\cal NP}-hard graph problems can be solved in polynomial time for graphs with bounded treewidth. Equivalent results are known for pathwidth and branchwidth. In recent years, several studies have shown that this result is not only of theoretical interest but can successfully be applied to find (almost) optimal solutions or lower bounds for diverse optimization problems. To apply a tree decomposition approach, the treewidth of the graph has to be determined, independently of the application at hand. Although for fixed $k$, linear time algorithms exist to solve the decision problem ``treewidth $\leq k$'', their practical use is very limited. The computational tractability of treewidth has been rarely studied so far. In this paper, we compare four heuristics and two lower bounds for instances from applications such as the frequency assignment problem and the vertex coloring problem. Three of the heuristics are based on well-known algorithms to recognize triangulated graphs. The fourth heuristic recursively improves a tree decomposition by the computation of minimal separating vertex sets in subgraphs. Lower bounds can be computed from maximal cliques and the minimum degree of induced subgraphs. A computational analysis shows that the treewidth of several graphs can be identified by these methods. For other graphs, however, more sophisticated techniques are necessary.
Author: | Arie M.C.A. Koster, Hans L. Bodlaender, Stan P.M. van Hoesel |
---|---|
Document Type: | ZIB-Report |
Tag: | computations; heuristics; lower bounds; treewidth |
MSC-Classification: | 05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05] |
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C35 Programming involving graphs or networks [See also 90C27] | |
94-XX INFORMATION AND COMMUNICATION, CIRCUITS / 94Cxx Circuits, networks / 94C15 Applications of graph theory [See also 05Cxx, 68R10] | |
Date of first Publication: | 2001/12/11 |
Series (Serial Number): | ZIB-Report (01-38) |
ZIB-Reportnumber: | 01-38 |
Published in: | An extended abstract appeared in: Electronic Notes in Discrete Mathematics. H. Broersma, U. Faigle, J. Hurink, S. Pickl (eds.), vol. 8. Elsevier Publ. 2001. |