Enumerating Minimal Subset Feedback Vertex Sets

摘要

The Subset Feedback Vertex Set problem takes as input a pair (G, S), where G = (V, E) is a graph with weights on its vertices, and S (⊂) V. 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. We show that this problem can be solved in time 0(1.8638~n), where n = |V|. This is a consequence of the main result of this paper, namely that all minimal subset feedback vertex sets of a graph can be enumerated in time 0(1.8638~n).