On Two Techniques of Combining Branching and Treewidth |
| |
Authors: | Fedor V Fomin Serge Gaspers Saket Saurabh Alexey A Stepanov |
| |
Affiliation: | (1) Department of Informatics, University of Bergen, Bergen, 5020, Norway;(2) The Institute of Mathematical Sciences, Chennai, 600 113, India |
| |
Abstract: | Branch & Reduce and dynamic programming on graphs of bounded treewidth are among the most common and powerful techniques used
in the design of moderately exponential time exact algorithms for NP hard problems. In this paper we discuss the efficiency
of simple algorithms based on combinations of these techniques. The idea behind these algorithms is very natural: If a parameter like
the treewidth of a graph is small, algorithms based on dynamic programming perform well. On the other side, if the treewidth
is large, then there must be vertices of high degree in the graph, which is good for branching algorithms. We give several
examples of possible combinations of branching and programming which provide the fastest known algorithms for a number of
NP hard problems. All our algorithms require non-trivial balancing of these two techniques.
In the first approach the algorithm either performs fast branching, or if there is an obstacle for fast branching, this obstacle
is used for the construction of a path decomposition of small width for the original graph. Using this approach we give the
fastest known algorithms for Minimum Maximal Matching and for counting all 3-colorings of a graph.
In the second approach the branching occurs until the algorithm reaches a subproblem with a small number of edges (and here
the right choice of the size of subproblems is crucial) and then dynamic programming is applied on these subproblems of small
width. We exemplify this approach by giving the fastest known algorithm to count all minimum weighted dominating sets of a
graph.
We also discuss how similar techniques can be used to design faster parameterized algorithms.
A preliminary version of this paper appeared as Branching and Treewidth Based Exact Algorithms in the Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC 2006) 15].
Additional support by the Research Council of Norway. |
| |
Keywords: | Exact exponential time algorithms Parameterized algorithms NP hard problems Treewidth #3-Coloring #Minimum dominating set Minimum maximal matching k-Weighted vertex cover |
本文献已被 SpringerLink 等数据库收录! |
|