E is replaced by the four edges (u,yuv1),(u,yuv2),(v,yuv1),
and (v,yuv2) for new vertices yuvi that appear only incident to these edges.
Definition
Given an undirected graph G = (V, E), a feedback vertex set is a set X ⊆ V with the property hat G \ X has no cycle. (Note: when G \ X it also eliminates the corresponding edges in X.)
Polynomial Certifier
Given an undirected graph G = (V, E) and an integer k. Does G contains a feedback vertex set X of size at most k?
Reduction from Vertex Cover from simple case to general case
Given a graph G = (V,E) and integer k, construct a graph G’ = (V’,E’) in which
each edge (u,v) E is replaced by the four edges (u,yuv1),(u,yuv2),(v,yuv1),
and (v,yuv2) for new vertices yuvi that appear only incident to these edges.
Claim 4.13.7.1. Vertex Cover ≤p Feedback Vertex Set
G contains a vertex cover, VC of size k if and only if X is a feedback vertex set
of size k.
G contains a vertex cover, VC of size k ⇒ X is a feedback vertex set of size k.
Proof. Suppose that X is a vertex cover of G. Then viewing X as a subset of V’, it is easy to verify that G′\ X has no cycles. __
X is a feedback vertex set of size k. ⇒ G contains a vertex cover, VC of size k.
Proof. Suppose that Y is a feedback set of G’ of minimum cardinality. We may
choose Y so that it contains no vertex of the form yuvi - for it does, then
Y ∪{u}\{yuvi} is a feedback vertex set of no greater cardinality. Thus, we
may view Y as a subset of V . For every edge (u,v) E, Y must intersect the
four-node cycle formed by u, v, yuv1, and yuv2. Since we have chosen Y so that
it contains no node of the form yuvi, it follows that Y contains one of u or v.
Thus, Y is a vertex cover of G. __
