Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Complexity of Cycle Transverse Matching Problems
verfasst von : Ross Churchley, Jing Huang, Xuding Zhu
Erschienen in: Combinatorial Algorithms
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
The stable transversal problem for a fixed graph
H
asks whether a graph contains a stable set that meets every induced copy of
H
in the graph. Stable transversal problems generalize several vertex partition problems and have been studied for various classes of graphs. Following a result of Farrugia, the stable transversal problem for each
C
ℓ
with ℓ ≥ 3 is NP-complete. In this paper, we study an ‘edge version’ of these problems. Specifically, we investigate the problem of determining whether a graph contains a matching that meets every copy of
H
. We show that the problem for
C
3
is polynomial and for each
C
ℓ
with ℓ ≥ 4 is NP-complete. Our results imply that the stable transversal problem for each
C
ℓ
with ℓ ≥ 4 remains NP-complete when it is restricted to line graphs. We show by contrast that the stable transversal problem for
C
3
, when restricted to line graphs, is polynomial.