2006 | OriginalPaper | Buchkapitel
Chordal Deletion Is Fixed-Parameter Tractable
verfasst von : Dániel Marx
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
It is known to be NP-hard to decide whether a graph can be made chordal by the deletion of
k
vertices. Here we present a uniformly polynomial-time algorithm for the problem: the running time is
f
(
k
)
n
α
for some constant
α
not depending on
k
and some
f
depending only on
k
. For large values of
n
, such an algorithm is much better than trying all the
O
(
n
k
) possibilities. Therefore, the chordal deletion problem parameterized by the number
k
of vertices to be deleted is fixed-parameter tractable. This answers an open question of Cai [2].