Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
verfasst von : Kevin Burrage, Vladimir Estivill-Castro, Michael Fellows, Michael Langston, Shev Mac, Frances Rosamond
Erschienen in: Parameterized and Exact 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
Resolving a noted open problem, we show that the
Undirected Feedback Vertex Set
problem, parameterized by the size of the solution set of vertices, is in the parameterized complexity class
Poly
(
k
), that is, polynomial-time pre-processing is sufficient to reduce an initial problem instance (
G
,
k
) to a decision-equivalent simplified instance (
G
′,
k
′) where
k
′ ≤
k
, and the number of vertices of
G
′ is bounded by a polynomial function of
k
. Our main result shows an
O
(
k
11
) kernelization bound.