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)
