Feedback arc set

A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used.

If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

Feedback arc sets have applications in circuit analysis, chemical engineering, deadlock resolution, ranked voting, ranking competitors in sporting events, mathematical psychology, ethology, and graph drawing.

Both are hard to approximate closer than some constant factor, an inapproximability result that can be strengthened under the unique games conjecture.

Reversing the edges of the feedback arc set produces a directed acyclic graph whose unique topological order can be used as the desired ranking.

Applications of this method include the following: Another early application of feedback arc sets concerned the design of sequential logic circuits, in which signals can propagate in cycles through the circuit instead of always progressing from inputs to outputs.

In such circuits, a minimum feedback arc set characterizes the number of points at which amplification is necessary to allow the signals to propagate without loss of information.

[21][22] However, because of the computational difficulty of finding this set, and the need for speed within operating system components, heuristics rather than exact algorithms are often used in this application.

However, this transformation does not preserve approximation quality for the maximum acyclic subgraph problem.

The choice of solution within any one of these subproblems does not affect the others, and the edges that do not appear in any of these components are useless for inclusion in the feedback arc set.

, but a dynamic programming method based on the Held–Karp algorithm can find the optimal permutation in time

A fixed-parameter tractable algorithm using dynamic programming can find minimum feedback arc sets in time

The circuit rank is an undirected analogue of the feedback arc set, the minimum number of edges that need to be removed from a connected graph to reduce it to a spanning tree; it is much easier to compute than the minimum feedback arc set.

This means that the size of the feedback arc set that it finds is at most this factor larger than the optimum.

[21] Determining whether feedback arc set has a constant-ratio approximation algorithm, or whether a non-constant ratio is necessary, remains an open problem.

This algorithm finds and deletes a vertex whose numbers of incoming and outgoing edges are as far apart as possible, recursively orders the remaining graph, and then places the deleted vertex at one end of the resulting order.

[35] Another, more complicated, polynomial time approximation algorithm applies to graphs with maximum degree

[45] A subexponential parameterized algorithm for weighted feedback arc sets on tournaments is also known.

[14] The maximum acyclic subgraph problem for dense graphs also has a polynomial-time approximation scheme.

Its main ideas are to apply randomized rounding to a linear programming relaxation of the problem, and to derandomize the resulting algorithm using walks on expander graphs.

[34][46] In order to apply the theory of NP-completeness to the minimum feedback arc set, it is necessary to modify the problem from being an optimization problem (how few edges can be removed to break all cycles) to an equivalent decision version, with a yes or no answer (is it possible to remove

Thus, the decision version of the feedback arc set problem takes as input both a directed graph and a number

As a consequence of its hardness proof, unless P = NP, it has no polynomial time approximation ratio better than 1.3606.

[34][51][52][53] By a different reduction, the maximum acyclic subgraph problem is also APX-hard, and NP-hard to approximate to within a factor of 65/66 of optimal.

If the unique games conjecture is true, then the minimum feedback arc set problem is hard to approximate in polynomial time to within any constant factor, and the maximum feedback arc set problem is hard to approximate to within a factor of

[55] In planar directed graphs, the feedback arc set problem obeys a min-max theorem: the minimum size of a feedback arc set equals the maximum number of edge-disjoint directed cycles that can be found in the graph.

in which the minimum size of a feedback arc set is two, while the maximum number of edge-disjoint directed cycles is only one.

Therefore, this ordering gives a path through arcs of the original tournament, covering all vertices.

[57] In a tournament, it may be the case that the minimum feedback arc set and maximum acyclic subgraph are both close to half the edges.

[60][61] A directed graph has an Euler tour whenever it is strongly connected and each vertex has equal numbers of incoming and outgoing edges.

Partition of a directed graph into a minimum feedback arc set (red dashed edges) and a maximum acyclic subgraph (blue solid edges)
The scores from men's beach volleyball at the 2016 Olympics , pool F, and the minimum-upset ranking for these scores. Arrows are directed from the loser to the winner of each match, and are colored blue when the outcome is consistent with the ranking and red for an upset, an outcome inconsistent with the ranking. With this ranking, only one match is an upset, the one in which USA beat QAT. The actual ranking used in the Olympics differed by placing ESP ahead of QAT on set ratio, causing their match to be ranked as another upset. [ 1 ]
A directed graph with three strongly connected components , the rightmost of which can be split at articulation vertex into two biconnected components , each a cycle of two vertices. The feedback arc set problem can be solved separately in each strongly connected component, and in each biconnected component of a strongly connected component.
The NP-completeness reduction of Karp and Lawler, from vertex cover of the large yellow graph to minimum feedback arc set in the small blue graph, expands each yellow vertex into two adjacent blue graph vertices, and each undirected yellow edge into two opposite directed edges. The minimum vertex cover (upper left and lower right yellow vertices) corresponds to the red minimum feedback arc set.