Advertisement
Published in:
2011 | OriginalPaper | Chapter
Enumerating Minimal Subset Feedback Vertex Sets
Authors : Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, Yngve Villanger
Published in: Algorithms and Data Structures
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.