On the parameterized complexity of finding separators with non-hereditary properties
Pinar Heggernes, Pim van 't Hof, Dániel Marx, Neeldhara Misra and Yngve Villanger
Algorithmica, vol. 72, no. 3, pp. 687-713, 2015.
[DOI][Preprint]
A preliminary version of this paper appeared in the proceedings of WG 2012, the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (held on June 26-28, 2012 in Jerusalem, Israel), Lecture Notes in Computer Science, vol. 7551, pp. 332-343, 2012.
[DOI]
Abstract:
We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable (Marx, O'Sullivan and Razgon, ACM Trans. Algor., to appear). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows:
- Finding a minimum c-connected s-t separator is FPT for c = 2 and W[1]-hard for any c ≥ 3.
- Finding a minimum s-t separator with diameter at most d is W[1]-hard for any d ≥2.
- Finding a minimum r-regular s-t separator is W[1]-hard for any r ≥ 1.
- For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree.
- Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless NP ⊆ coNP/poly.