Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties
verfasst von : Pinar Heggernes, Pim van’t Hof, Dániel Marx, Neeldhara Misra, Yngve Villanger
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 is a connected graph or an independent set are fixed-parameter tractable (Marx, O’Sullivan and Razgon, manuscript). We extend these results the following way:
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.
We also show that 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.