11.29

Membership in NP.
Given a set F ⊆ V we can check in O(|V|+|A|) time that
1. |F|≤k, and
2. G-F is acyclic, e.g. by a topological–sort/BFS that succeeds iff no arc is left after repeatedly deleting in-degree-0 vertices. Hence a certificate can be verified in polynomial time, so Feedback Vertex Set is in NP.

NP-hardness via reduction from Vertex Cover.
Instance of Vertex Cover: an undirected graph [math]H=(V,E)[/math] and integer [math]k[/math].
Transform it in polynomial time into a directed graph [math]G=(V,A)[/math] by replacing every undirected edge {u,v} with the two opposite arcs (u,v) and (v,u):

A ← Ø for each {u,v} in E: A ← A ∪ {(u,v),(v,u)} return (V,A), k

This construction keeps exactly the |V| vertices of H and adds 2|E| arcs.

Equivalence of solutions.
• If S ⊆ V is a vertex cover of H with |S|≤k, then every undirected edge has at least one endpoint in S. Therefore every 2-cycle (u,v,u) in G contains a vertex of S, so G−S is acyclic; hence S is a feedback vertex set of size ≤k.
• Conversely, assume F is a feedback vertex set of G with |F|≤k. If some edge {u,v} of H had neither endpoint in F, the two arcs (u,v) and (v,u) would survive in G−F and form a directed 2-cycle, contradicting that G−F is acyclic. Thus every edge is incident to F, i.e. F is a vertex cover of size ≤k.

The mapping preserves the answer and is computable in polynomial time, so Feedback Vertex Set is NP-hard. Since it is also in NP, it is NP-complete.

Verifier pseudocode

verify(G,k,F): if |F| > k: return FALSE H ← G minus vertices F return (topological_sort(H) exists)

Thus the directed Feedback Vertex Set problem is NP-complete.

Back to Chapter 11