Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
verfasst von : Jiong Guo
Erschienen in: Algorithms and Computation
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
In an edge deletion problem one is asked to delete at most
k
edges from a given graph such that the resulting graph satisfies a certain property. In this work, we study four NP-complete edge deletion problems where the goal graph has to be a chain, a split, a threshold, or a co-trivially perfect graph, respectively. All these four graph classes are characterized by a common forbidden induced subgraph 2
K
2
, that is, an independent pair of edges. We present the seemingly first non-trivial algorithmic results for these four problems, namely, four polynomial-time data reduction algorithms that achieve problem kernels containing
O
(
k
2
),
O
(
k
4
),
O
(
k
3
), and
O
(
k
3
) vertices, respectively.