Sharp Separation and Applications to Exact and Parameterized Algorithms

Fomin, Fedor V. and Grandoni, Fabrizio and Lokshtanov, Daniel and Saurabh, Saket (2012) Sharp Separation and Applications to Exact and Parameterized Algorithms. Algorithmica, 63 (3). pp. 692-706. ISSN 1432-0541

Full text not available from this repository.


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 parameterized algorithm with running time O(16 k + o(k) + n O(1)) for the Maximum Internal Subtree problem in directed graphs. This is a significant improvement over the best previously known parameterized algorithm for the problem by [Cohen et al.’09], running in time O(49.4 k  + n O(1)). The second application is a O(2 n + o(n)) time and space 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, Maximum Internal Spanning Tree and their edge weighted variants.

Actions (login required)

View Item View Item