Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Parameterized Domination in Circle Graphs
verfasst von : Nicolas Bousquet, Daniel Gonçalves, George B. Mertzios, Christophe Paul, Ignasi Sau, Stéphan Thomassé
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
A
circle graph
is the intersection graph of a set of chords in a circle. Keil [
Discrete Applied Mathematics
, 42(1):51-63, 1993] proved that
Dominating Set
,
Connected Dominating Set
, and
Total Dominating Set
are
NP
-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction:
Dominating Set
,
Independent Dominating Set
,
Connected Dominating Set
,
Total Dominating Set
, and
Acyclic Dominating Set
are
W
[1]-hard in circle graphs, parameterized by the size of the solution.
Whereas both
Connected Dominating Set
and
Acyclic Dominating Set
are
W
[1]-hard in circle graphs, it turns out that
Connected Acyclic Dominating Set
is polynomial-time solvable in circle graphs.
If
T
is a
given
tree, deciding whether a circle graph has a dominating set isomorphic to
T
is
NP
-complete when
T
is in the input, and
FPT
when parameterized by |
V
(
T
)|. We prove that the FPT algorithm is subexponential.