Name
Abstract | ||
|---|---|---|
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.8638n) for input graphs on n vertices. To the best of our knowledge, no exact algorithm breaking the trivial 2nnO(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.8638n) time. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00453-012-9731-6 | workshop on algorithms and data structures |
Keywords | DocType | Volume |
Exact exponential algorithms,NP-hard problems,Subset feedback vertex set | Journal | 69 |
Issue | ISSN | Citations |
1 | 0178-4617 | 7 |
PageRank | References | Authors |
0.49 | 14 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fedor V. Fomin | 1 | 3139 | 192.21 |
| Pinar Heggernes | 2 | 845 | 72.39 |
| Dieter Kratsch | 3 | 1957 | 146.89 |
| Charis Papadopoulos | 4 | 151 | 17.75 |
| Yngve Villanger | 5 | 592 | 37.08 |