E.Definition
Given a directed graph G = (V,E), there exists a subset E′⊆ E, called a feedback arc set, if the removal of edges E′ renders G acyclic.
Polynomial Certifier
Given a directed graph G = (V,E), and a number k. Does there exist a subset E′⊆ E of size k, if the removal of edges E′ renders G acyclic.
Reduction from Vertex Cover from simple case to general case
We construct a instance < G′,k > of FAS as follows:
If G = (V, E) has n vertices, v1,…,vn, then make G′ = (V ′,E′) a directed graph with
2n vertices, w1,w1′,…,wn,wn′, and n + 2|E| (directed) edges:
E.Obviously, this construction can be done in polynomial time.
Claim 4.13.6.1. Vertex Cover ≤p Feedback Arc Set
G contains a vertex cover, VC of size k if and only if FAS = {(wi,wi′)|vi V }
is a feedback arc set (of the same size) for G’
G contains a vertex cover, VC of size k ⇒ FAS = {(wi,wi′)|vi V } is a feedback
arc set (of the same size) for G’
Proof. We know from the construction that if (vi,vj) E in G, then (wi,wi′),
(wj,wj′), (wj′,wi), (wi′,wj) E′ in G’, which by observation, form a cycle.
Thus, if a vertex cover VC exists, then either vi, or vj would be in VC set, that
exactly means removing either (wi,wi′) or (wj,wj′) FAS (depending on vi
or vj VC has) would break the cycle. So, if G has VG of size b, then G’ also has
FAS of size b. __
FAS = {(wi,wi′)|vi V } is a feedback arc set of size k for G’ ⇒ G contains a
vertex cover, VC of size k.
Proof. We are given a set of FAS, which might not all contain the edge of the form (wi,wi′). Therefore, our first goal is to transform those edge into (wi,wi′).
We know from the previous problem that any cycle with (wi′,wj) must also contain (wi,wi′),(wj,wj′),(wj′,wi), so if we remove (wi′,wj), and add (wi,wi′), FAS is still a feedback arc set. Continue in this fashion, we would never increase the size of the set, however, we might decrease the size. Considering two loops, of wi → wi′→ wj → wj′→ wi, wj → wj′→ wk → wk′→ wj, with j to be shared edges of two loops. Then, removing (wj′,wi) and (wj′,wk) then adding (wj,wj′) would give us size less than b (Which still satisfies ≤ b condition).
Thus, we now claim that V C = {vi|(wi,wi′) FAS} must be a vertex cover
for G. Suppose this is not true, then there exists two nodes vj,vk that are both
⁄ V C, which implies (wj,wj′),(wk,wk′) both ⁄ FAS in G’. However, in G’,
from the construction above, wj → wj′→ wk → wk′→ wj forms a cycle, even
after removing all edges in FAS. Therefore, contradiction occurs. __
