Feedback arc set
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) or feedback edge set 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 directed graph, and the minimum spanning tree
, which is the undirected variant of the feedback arc set problem.
A minimal feedback arc set (one that can not be reduced in size by removing any edges) has the additional property that, if the edges in it are reversed rather than removed, then the graph remains acyclic. Finding a small edge set with this property is a key step in layered graph drawing
.
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.
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.
Although NP-complete, the feedback arc set problem is fixed-parameter tractible
: 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. , 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.
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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
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
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
(DAG). One way to do this is simply to drop edges from the graph to break the cycles. A feedback arc set (FAS) or feedback edge set 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
Feedback vertex set
In the mathematical discipline of graph theory, a feedback vertex set of a graph is a set of vertices whose removal leaves a graph without cycles. In other words, each feedback vertex set contains at least one vertex of any cycle in the graph....
, which is a set of vertices containing at least one vertex from every cycle in the directed graph, and the minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
, which is the undirected variant of the feedback arc set problem.
A minimal feedback arc set (one that can not be reduced in size by removing any edges) has the additional property that, if the edges in it are reversed rather than removed, then the graph remains acyclic. Finding a small edge set with this property is a key step in layered graph drawing
Layered graph drawing
Layered graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards...
.
Example
As a simple example, consider the following hypothetical 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.
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-hardNP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, asks whether all cycles can be broken by removing at most k edges; this was one of Karp's 21 NP-complete problems
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
, shown by reducing from the vertex cover problem.
Although NP-complete, the feedback arc set problem is fixed-parameter tractible
Parameterized complexity
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
: 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
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
that always find an edge set at most c times bigger than the optimal result. , 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
Tournament (graph theory)
A tournament is a directed graph obtained by assigning a direction for each edge in an undirected complete graph. That is, it is a directed graph in which every pair of vertices is connected by a single directed edge....
, 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)
Polynomial-time approximation scheme
In computer science, a polynomial-time approximation scheme is a type of approximation algorithm for optimization problems ....
; and this still holds for a restricted weighted version of the problem.
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
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
, which can be done easily in polynomial time.