Sharp Separation and Applications to Exact and Parameterized Algorithms

摘要

Many divide-and-conquer algorithms employ the fact that the vertex set of a graph of bounded treewidth can be separated in two roughly balanced subsets by removing a small subset of vertices, referred to as a separator. In this paper we prove a trade-off between the size of the separator and the sharpness with which we can fix the size of the two sides of the partition. Our result appears to be a handy and powerful tool for the design of exact and parameterized algorithms for NP-hard problems. We illustrate that by presenting two applications. Our first application is a O(2~(n+o(n)))-time algorithm for the DEGREE CONSTRAINED Spanning Tree problem: find a spanning tree of a graph with the maximum number of nodes satisfying given degree constraints. This problem generalizes some well-studied problems, among them Hamiltonian Path, Full Degree Spanning Tree, Bounded Degree Spanning Tree, and Maximum Internal Spanning Tree. The second application is a parameterized algorithm with running time O(16~(k+o(k)) + n~(O(1))) for the k-Internal Out-Branching problem: here the goal is to compute an out-branching of a digraph with at least k internal nodes. This is a significant improvement over the best previously known parameterized algorithm for the problem by Cohen et al.