Feedback arc set
From Wikipedia, the free encyclopedia
In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG). One way to do this is simply to drop edges from the graph to break the cycles. A feedback arc set (FAS) is a set of edges which, when removed from the graph, leave a DAG. Put another way, it's a set containing at least one edge of every cycle in the graph.
Closely related are the feedback vertex set, which is a set of vertices containing at least one vertex from every cycle in the graph, and the minimum spanning tree, which is the undirected variant of the feedback arc set problem.
[edit] Example
As a simple example, consider the following imaginary situation:
- George says he will give you a piano, but only in exchange for a lawnmower.
- Harry says he will give you a lawnmower, but only in exchange for a microwave.
- Jane says she will give you a microwave, but only in exchange for a piano.
We can express this as a graph problem. Let each vertex represent an item, and add an edge from A to B if you must have A to obtain B. Your goal is to get the lawnmower. Unfortunately, you don't have any of the three items, and because this graph is cyclic, you can't get any of them either.
However, suppose you offer George $100 for his piano. If he accepts, this effectively removes the edge from the lawnmower to the piano, because you no longer need the lawnmower to get the piano. Consequently, the cycle is broken, and you can trade twice to get the lawnmower. This one edge constitutes a feedback arc set.
[edit] 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 Karp's 21 NP-complete problems, shown by reducing from the vertex cover problem.
The news gets worse: Viggo Kann showed in 1992 that the minimum feedback arc set problem is APX-hard, which means that there is a constant k, such that there is no polynomial-time approximation algorithm that always find an edge set at most k times bigger than the optimal result. As of 2006, the highest value of "k" for which this is k = 1.36.
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.
[edit] References
- I. Dinur and S. Safra. "The Importance of Being Biased." In "Proceedings of the 34th Annual
Symposium on the Theory of Computing." pp. 33--42, 2002.
- Richard M. Karp. "Reducibility Among Combinatorial Problems." In Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y.. New York: Plenum, p.85-103. 1972.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. "Minimum Feedback Arc Set". A compendium of NP optimization problems. Last modified March 20, 2000.
- Viggo Kann. On the Approximability of NP-complete Optimization Problems. PhD thesis. Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm. 1992.
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.1: GT8, pg.192.
