Chapter VII Feedback Node Set

Break every cycle

If a cycle exists, at least one vertex on it has to go.

Given a directed graph, a feedback vertex set is a subset of vertices whose removal leaves no cycles:

F \subseteq V such that G [V ∖ F] is acyclic. (1)

Karp's reduction is from vertex cover: subdivide each edge, and a vertex cover in the original becomes a set satisfying (1) in the subdivision.

Like vertex cover, the problem is fixed-parameter tractable in the answer size k — recent work runs in time

O (3.4 6^{k} \cdot n^{O (1)}), (2)

making (1) cheap to test when the cuts are small. But it remains inapproximable beyond constant factors in the general case. The undirected variant is also NP-hard, with somewhat friendlier approximation properties.

Figures, in plain terms

(1)

F ⊆ V picks a subset of vertices to remove.

The new notation here is G[X], the induced subgraph on X. Take G, throw away every vertex not in X, and throw away every edge that touched a thrown-away vertex. What's left is a smaller graph living inside G.

So G[V \ F] is what's left after removing the vertices in F. (V \ F is set difference from chapter 5: vertices in V but not in F.)

The condition is acyclic — no directed cycles remain. That is, after the surgery, you can lay the vertices on a line such that every edge points forward.

(2)

Two layers of big-O. The outer O(3.46^k · n^O(1)) has an inner O(1) in the exponent on n.

O(1) in an exponent means "some constant" — the actual algorithm uses n² or n³, but the analysis says "polynomial in n" without committing to which polynomial.

So the runtime is exponential in k (the answer size) but only polynomial in n (the input size). Tractable when k is small, regardless of how big the graph is.