On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties
We study the problem of finding small st separators that induce graphs having certain properties. It is known that finding a minimum clique st separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221232, 1985), while for example the problems of finding a minimum st separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). 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: (1) Finding a minimum c-connected st separator is FPT for c=2 and W[1]-hard for any c?3.  (2) Finding a minimum st separator with diameter at most d is W[1]-hard for any d?2.  (3) Finding a minimum r-regular st separator is W[1]-hard for any r?1.  (4) For any decidable graph property, finding a minimum st separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree.  (5) Finding a connected st separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless \(\mathrm{NP} \subseteq \mathrm{coNP/poly}\).  In order to prove (1), we show that the natural c-connected generalization of the well-known Steiner Tree problem is FPT for c=2 and W[1]-hard for any c?3.
parameterized complexity non-hereditary properties vertex separators fpt algorithms