Anzeige
Erschienen in:
2011 | OriginalPaper | Buchkapitel
Enumerating Minimal Subset Feedback Vertex Sets
verfasst von : Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, Yngve Villanger
Erschienen in: Algorithms and Data Structures
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
Subset Feedback Vertex Set
problem takes as input a weighted graph
G
and a vertex subset
S
of
G
, and the task is to find a set of vertices of total minimum weight to be removed from
G
such that in the remaining graph no cycle contains a vertex of
S
. This problem is a generalization of two classical NP-complete problems:
Feedback Vertex Set
and
Multiway Cut
. We show that it can be solved in time
O
(1.8638
n
) for input graphs on
n
vertices. To the best of our knowledge, no exact algorithm breaking the trivial 2
n
n
O
(1)
-time barrier has been known for
Subset Feedback Vertex Set
, even in the case of unweighted graphs. The mentioned running time is a consequence of the more general main result of this paper: we show that all minimal subset feedback vertex sets of a graph can be enumerated in
O
(1.8638
n
) time.