Treewidth and Combinatorial Optimization
Many hard optimization problems from different fields of research are modeled by use of networks/graphs. Frequently, the underlying network structure of these problems can be characterized by a sparsity that allows for decompositions with relatively small treewidth. Such decompositions can very often be used to solve the optimization problem for quite large instances, that are not feasibly solvable by standard techniques that do not exploit a decomposition of the underlying network structure.
This project aims at two targets. First, we want to be able to efficiently and effectively find good tree decompositions of graphs. In the literature this issue has mainly been treated from a theoretical viewpoint. Our main objective is to develop techniques which generate good or even optimal tree decompositions for a wide variety of graphs. Second, we want to study the use of good tree decompositions for solving hard combinatorial optimization problems, modeled on graphs, as has been done for the frequency assignment problem.
Treewidth and Combinatorial Optimization
Many combinatorial optimization problems take a graph as part of the input. In many cases more efficient algorithms are available to solve the problem if this graph belongs to a specific class of graphs. In case of trees for example, many NP-hard optimization problems can be solved in polynomial time.
A tree decomposition of a graph shows the alikeness of the graph with a tree. The width of a tree decomposition defines a measure for the alikeness. The treewidth is the smallest width that can be reached for a graph.
Over the last decades, it has been shown that many NP-hard combinatorial problems can be solved in polynomial time for graph with treewidth bounded by a constant. Until recently, it was assumed that these results were of theoretical interest only. By means of the frequency assignment problem it has been shown that such an algorithm to compute the optimal solution can be used in practice as well. Moreover, the concept of tree decomposition proved itself by the computation of so-called exact inference in probabilistic networks.
Methods that use the tree decomposition consist of two steps: (i) the construction of a tree decomposition of the graph, and (ii) the application of dynamic programming to find the optimal solution of the combinatorial problem. Whereas the first step can be applied without knowledge of the application, the second step requires the development of a for the application tailor-made algorithm.
At the moment, we have concentrated our effort to the efficient computation of tree decompositions. On the one hand, preprocessing rules have been derived, on the other hand heuristics and lower bounds have been the topic of research.
The preprocessing rules have been applied to probabilistic networks, that originate from medicine. The rules typically result in substantial reductions of the problem size, which relieves the construction of a tree decomposition substantially. Some instances can be solved this way.
To solve frequency assignment problems, we already developed a first heuristic and a lower bound on the treewidth. However, application of them did not result to satisfactory results in all cases. Therefore, we developed other heuristics that use the connection between treewidth and the triangulation of a graph. The heuristics have been compared at instances of different applications (frequency assignment, graph coloring, and probabilistic networks). Unfortunately, the results are still not satisfactory in all cases.
To evaluate the quality of the heuristics, lower bound on the treewidth are necessary. Within the project, we have developed several methods to compute such bounds.
Moreover, within the project the concept of weighted treewidth has been introduced. It allows for a more precise approximation of the running time of algorithms based on a tree decomposition of the graph. We generalized the preprocessing rules for treewidth to weighted treewidth.
Links
- TACO project website
- TreeiwidthLIB: A benchmark for algorithms for Treewidth and related graph problems
Poster
- Treewidth and Combinatorial Optimization (pdf, in German)
Publikationen
2006 |
|||
Hans L. Bodlaender, Fedor V. Fomin, Arie M.C.A. Koster, Dieter Kratsch, Dimitrios M. Thilikos | On exact algorithms for treewidth | ZIB-Report 06-32 (An extended abstract appeared in: Proceedings 14th Annual European Symposium on Algorithms, ESA 2006, Lecture Notes in Computer Science, Vol. 4168, 2006, pp. 672-683) |
PDF
BibTeX URN |
2005 |
|||
Hans L. Bodlaender, Alexander Grigoriev, Arie M.C.A. Koster | Treewidth Lower Bounds with Brambles | ZIB-Report 05-54 (Appeared in: Algorithmica 51 (2008) 81-98. An extended abstract appeared in: Proc. 13th Ann. Europ. Symp. on Algorithms, ESA 2005, LNCS 3669, Springer 2005, pp. 391-402) |
PDF
BibTeX URN |
2004 |
|||
Thomas Wolle, Arie M.C.A. Koster, Hans L. Bodlaender | A Note on Contraction Degeneracy | ZIB-Report 04-43 |
PDF
BibTeX URN |
Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle | Contraction and Treewidth Lower Bounds | ZIB-Report 04-29 (Appeared in: Journal of Graph Algorithms and Applications 10:1 (2006) 5-49. An extended abstract appeared in: Proceedings of 12th Annual European Symposium on Algorithms (ESA), Bergen, Norway, 628-639 (2004)) |
PDF
BibTeX URN |
Arie M.C.A. Koster, Thomas Wolle, Hans L. Bodlaender | Degree-Based Treewidth Lower Bounds | ZIB-Report 04-44 (Appeared in: Proc. 4th Int. Workshop on Experimental and Efficient Algorithms WEA 2005. S. E. Nikoletseas (ed.) LNCS 3503, Springer 2005, pp. 101-112) |
PDF
BibTeX URN |
Hans L. Bodlaender, Arie M.C.A. Koster | On the Maximum Cardinality Search Lower Bound for Treewidth | ZIB-Report 04-45 (Appeared in: Discrete Applied Mathematics 155 (2007) 1348-1372. An extended abstract appeared in: Proceedings of International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, Lecture Notes in Computer Science 3353, 2005, 81-92) |
PDF
BibTeX URN |
2003 |
|||
Hans L. Bodlaender, Arie M.C.A. Koster | Safe separators for treewidth | ZIB-Report 03-32 (Appeared in: Discrete Mathematics 306:3 (2006) 337-350. An extended abstract appeared in: Joint Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX '04) and the Workshop on Analytic Algorithmics and Combinatorics (ANALCO '04), New Oreleans, SIAM Proceedings, pp. 70-78 (2004)) |
PDF
BibTeX URN |
2002 |
|||
Frank van den Eijkhof, Hans L. Bodlaender, Arie M.C.A. Koster | Safe reduction rules for weighted treewidth | ZIB-Report 02-49 (Appeared in: Algorithmica 47:2 (2007) 139-158) |
PDF
BibTeX URN |
2001 |
|||
Arie M.C.A. Koster, Hans L. Bodlaender, Stan P.M. van Hoesel | Treewidth: Computational Experiments | ZIB-Report 01-38 (An extended abstract appeared in: Electronic Notes in Discrete Mathematics. H. Broersma, U. Faigle, J. Hurink, S. Pickl (eds.), vol. 8. Elsevier Publ. 2001.) |
PDF
BibTeX URN |