Feedback Arc Set - Computational Complexity

Computational Complexity

As in the above example, there is usually some cost associated with removing an edge. For this reason, we'd like to remove as few edges as possible. Removing one edge suffices in a simple cycle, but in general figuring out the minimum number of edges to remove is an NP-hard problem called the minimum feedback arc set problem. It is particularly difficult in k-edge-connected graphs for large k, where each edge falls in many different cycles. The decision version of the problem, which is NP-complete, asks whether all cycles can be broken by removing at most k edges; this was one of Richard M. Karp's 21 NP-complete problems]], shown by reducing from the vertex cover problem.

Although NP-complete, the feedback arc set problem is fixed-parameter tractable: there exists an algorithm for solving it whose running time is a fixed polynomial in the size of the input graph (independent of the number of edges in the set) but exponential in the number of edges in the feedback arc set.

Viggo Kann showed in 1992 that the minimum feedback arc set problem is APX-hard, which means that there is a constant c, such that, assuming P≠NP, there is no polynomial-time approximation algorithm that always find an edge set at most c times bigger than the optimal result. As of 2006, the highest value of c for which such an impossibility result is known is c = 1.3606. The best known approximation algorithm has ratio O(log n log log n). For the dual problem, of approximating the maximum number of edges in an acyclic subgraph, an approximation somewhat better than 1/2 is possible.

If the input digraphs are restricted to be tournaments, the resulting problem is known as the minimum feedback arc set problem on tournaments (FAST). This restricted problem does admit a polynomial-time approximation scheme (PTAS); and this still holds for a restricted weighted version of the problem. A subexponential fixed parameter algorithm for the weighted FAST was given by Karpinski & Schudy (2010).

On the other hand, if the edges are undirected, the problem of deleting edges to make the graph cycle-free is equivalent to finding a minimum spanning tree, which can be done easily in polynomial time.