The description of the Feedback Arc Set problem is as follows. Given a directed graph G, the question is whether it is possible to remove k or fewer edges such that there are no cycles in G. First of all, this problem is obviously an NP problem. That is, given the k edges to be removed, I only need to remove these k edges first, and then determine if there are any cycles in the remaining graph. The method to determine cycles is to start from a point, record the points passed through, and check if the current point has been visited before, indicating the presence of a cycle. And this operation can be done in polynomial time.
Now, we reduce the Vertex Cover problem to the Feedback Arc Set problem to prove that the Feedback Arc Set problem is NP-hard.
Consider that we already have a Vertex Cover problem <G, k>, which means that there are k points in G that can cover all the edges in the graph. We can transform it into a directed graph Gf using the following rules:
- For each point u in G, create u_in and u_out in Gf, and connect u_in to u_out.
- For each edge e in G, assuming it connects points u and v, we connect u_out to v_in and v_out to u_in in Gf.
According to the above rules, the transformation process is shown below. It is obvious that the above transformation can be done in polynomial time.
[Image: Transformation from Vertex Cover problem to Feedback Arc Set problem]
It can be seen that for each edge in G, we construct a cycle in Gf. Therefore, in order to eliminate all cycles in Gf, it is necessary to remove all edges in G. So, assuming we have an algorithm Af that can remove k edges from Gf in polynomial time to achieve a cycle-free graph, we can use the rules to transform Gf to G in polynomial time, allowing Af to solve the Vertex Cover problem in polynomial time. However, we know that the Vertex Cover problem is NP-hard, which means that there is no such algorithm Af. Therefore, the Feedback Arc Set problem cannot be solved in polynomial time. Thus, the Feedback Arc Set problem is NP-complete.
In conclusion, the Feedback Arc Set problem is NP-complete.