Feedback arc set

In

Several problems involving finding rankings or orderings can be solved by finding a feedback arc set on a

• In sporting competitions with round-robin play, the outcomes of each game can be recorded by directing an edge from the loser to the winner of each game. Finding a minimum feedback arc set in the resulting graph, reversing its edges, and topological ordering, produces a ranking on all of the competitors. Among all of the different ways of choosing a ranking, it minimizes the total number of upsets, games in which a lower-ranked competitor beat a higher-ranked competitor.^[2][3][4] Many sports use simpler methods for group tournament ranking systems based on points awarded for each game;^[5] these methods can provide a constant approximation to the minimum-upset ranking.^[6]
• In primatology and more generally in ethology, dominance hierarchies are often determined by searching for an ordering with the fewest reversals in observed dominance behavior, another form of the minimum feedback arc set problem.^[7][8][9]
• In mathematical psychology, it is of interest to determine subjects' rankings of sets of objects according to a given criterion, such as their preference or their perception of size, based on pairwise comparisons between all pairs of objects. The minimum feedback arc set in a tournament graph provides a ranking that disagrees with as few pairwise outcomes as possible.^[2][10] Alternatively, if these comparisons result in independent probabilities for each pairwise ordering, then the maximum likelihood estimation of the overall ranking can be obtained by converting these probabilities into log-likelihoods and finding a minimum-weight feedback arc set in the resulting tournament.^[2][3]
• The same maximum-likelihood ordering can be used for seriation, the problem in statistics and exploratory data analysis of arranging elements into a linear ordering, in cases where data is available that provides pairwise comparisons between the elements.^[3][11][12]
• In ranked voting, the Kemeny–Young method can be described as seeking an ordering that minimizes the sum, over pairs of candidates, of the number of voters who prefer the opposite ordering for that pair.^[13] This can be formulated and solved as a minimum-weight feedback arc set problem, in which the vertices represent candidates, edges are directed to represent the winner of each head-to-head contest, and the cost of each edge represents the number of voters who would be made unhappy by giving a higher ranking to the head-to-head loser.^[14]

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.^[15] In synchronous circuits made from asynchronous components, synchronization can be achieved by placing clocked gates on the edges of a feedback arc set.^[16] Additionally, cutting a circuit on a feedback arc a set reduces the remaining circuit to combinational logic, simplifying its analysis, and the size of the feedback arc set controls how much additional analysis is needed to understand the behavior of the circuit across the cut.^[15] Similarly, in process flowsheeting in chemical engineering, breaking edges of a process flow diagram on a feedback arc set, and guessing or trying all possibilities for the values on those edges, allows the rest of the process to be analyzed in a systematic way because of its acyclicity. In this application, the idea of breaking edges in this way is called "tearing".^[17]

In layered graph drawing, the vertices of a given directed graph are partitioned into an ordered sequence of subsets (the layers of the drawing), and each subset is placed along a horizontal line of this drawing, with the edges extending upwards and downwards between these layers. In this type of drawing, it is desirable for most or all of the edges to be oriented consistently downwards, rather than mixing upwards and downwards edges, in order for the reachability relations in the drawing to be more visually apparent. This is achieved by finding a minimum or minimal feedback arc set, reversing the edges in that set, and then choosing the partition into layers in a way that is consistent with a topological order of the resulting acyclic graph.^[18][19] Feedback arc sets have also been used for a different subproblem of layered graph drawing, the ordering of vertices within consecutive pairs of layers.^[20]

In deadlock resolution in operating systems, the problem of removing the smallest number of dependencies to break a deadlock can be modeled as one of finding a minimum feedback arc set.^[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.^[22]

Algorithms

Equivalences

The minimum feedback arc set and maximum acyclic subgraph are equivalent for the purposes of exact optimization, as one is the

A feedback arc set of a given graph ${\displaystyle G}$ is the same as a feedback vertex set of a directed line graph of ${\displaystyle G}$. Here, a feedback vertex set is defined analogously to a feedback arc set, as a subset of the vertices of the graph whose deletion would eliminate all cycles. The line graph of a directed graph ${\displaystyle G}$ has a vertex for each edge of ${\displaystyle G}$, and an edge for each two-edge path in ${\displaystyle G}$. In the other direction, the minimum feedback vertex set of a given graph ${\displaystyle G}$ can be obtained from the solution to a minimum feedback arc set problem on a graph obtained by splitting every vertex of ${\displaystyle G}$ into two vertices, one for incoming edges and one for outgoing edges. These transformations allow exact algorithms for feedback arc sets and for feedback vertex sets to be converted into each other, with an appropriate translation of their complexity bounds. However, this transformation does not preserve approximation quality for the maximum acyclic subgraph problem.^[21][24]

In both exact and approximate solutions to the feedback arc set problem, it is sufficient to solve separately each strongly connected component of the given graph, and to break these strongly connected components down even farther to their biconnected components by splitting them at articulation vertices. 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.^[25] When one of these components can be separated into two disconnected subgraphs by removing two vertices, a more complicated decomposition applies, allowing the problem to be split into subproblems derived from the triconnected components of its strongly connected components.^[26]

Exact

One way to find the minimum feedback arc set is to search for an ordering of the vertices such that as few edges as possible are directed from later vertices to earlier vertices in the ordering.^[27] Searching all permutations of an ${\displaystyle n}$-vertex graph would take time ${\displaystyle O(n!)}$, but a dynamic programming method based on the Held–Karp algorithm can find the optimal permutation in time ${\displaystyle O(n2^{n})}$, also using an exponential amount of space.^[28][29] A divide-and-conquer algorithm that tests all partitions of the vertices into two equal subsets and recurses within each subset can solve the problem in time ${\displaystyle O(4^{n}/{\sqrt {n}})}$, using

In parameterized complexity, the time for algorithms is measured not just in terms of the size of the input graph, but also in terms of a separate parameter of the graph. In particular, for the minimum feedback arc set problem, the so-called natural parameter is the size of the minimum feedback arc set. On graphs with ${\displaystyle n}$ vertices, with natural parameter ${\displaystyle k}$, the feedback arc set problem can be solved in time ${\displaystyle O(n^{4}4^{k}k^{3}k!)}$, by transforming it into an equivalent feedback vertex set problem and applying a parameterized feedback vertex set algorithm. Because the exponent of ${\displaystyle n}$ in this algorithm is the constant ${\displaystyle 4}$, independent of ${\displaystyle k}$, this algorithm is said to be fixed-parameter tractable.^[30]

Other parameters than the natural parameter have also been studied. A fixed-parameter tractable algorithm using dynamic programming can find minimum feedback arc sets in time ${\displaystyle O(2^{r}m^{4}\log m)}$, where ${\displaystyle r}$ is the circuit rank of the underlying undirected graph. The circuit rank is an undirected analogue of the feedback arc set, the minimum number of edges that need to be removed from a graph to reduce it to a spanning tree; it is much easier to compute than the minimum feedback arc set.^[24] For graphs of treewidth ${\displaystyle t}$, dynamic programming on a tree decomposition of the graph can find the minimum feedback arc set in time polynomial in the graph size and exponential in ${\displaystyle O(t\log t)}$. Under the exponential time hypothesis, no better dependence on ${\displaystyle t}$ is possible.^[31]

Instead of minimizing the size of the feedback arc set, researchers have also looked at minimizing the maximum number of edges removed from any vertex. This variation of the problem can be solved in

The best known polynomial-time approximation algorithm for the feedback arc set has the non-constant

${\displaystyle O(\log n\log \log n)}$.

The maximum acyclic subgraph problem has an easy approximation algorithm that achieves an approximation ratio of ${\displaystyle {\tfrac {1}{2}}}$:

• Fix an arbitrary ordering of the vertices
• Partition the edges into two acyclic subgraphs, one consisting of the edges directed consistently with the ordering, and the other consisting of edges directed oppositely to the ordering.
• Return the larger of the two subgraphs.

This can be improved by using a greedy algorithm to choose the ordering. 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. For graphs with ${\displaystyle m}$ edges and ${\displaystyle n}$ vertices, this produces an acyclic subgraph with ${\displaystyle m/2+n/6}$ edges, in linear time, giving an approximation ratio of ${\displaystyle {\tfrac {1}{2}}+\Omega (n/m)}$.^[35] Another, more complicated, polynomial time approximation algorithm applies to graphs with maximum degree ${\displaystyle \Delta }$, and finds an acyclic subgraph with ${\displaystyle m/2+\Omega (m/{\sqrt {\Delta }})}$ edges, giving an approximation ratio of the form ${\displaystyle {\tfrac {1}{2}}+\Omega (1/{\sqrt {\Delta }})}$.^[36][37] When ${\displaystyle \Delta =3}$, the approximation ratio ${\displaystyle 8/9}$ can be achieved.^[38]

Restricted inputs

In directed

It can be solved in time ${\displaystyle O(n^{5/2}\log n)}$.

time ${\displaystyle O(n^{3})}$,^[39]

number ${\displaystyle N}$,

time ${\displaystyle O(n^{5/2}\log nN)}$.

utility graph

${\displaystyle K_{3,3}}$ as a graph minor, using the fact that the triconnected components of these graphs are either planar or of bounded size.^[26] Planar graphs have also been generalized in a different way to a class of directed graphs called weakly acyclic digraphs, defined by the integrality of a certain polytope associated with their feedback arc sets. Every planar directed graph is weakly acyclic in this sense, and the feedback arc set problem can be solved in polynomial time for all weakly acyclic digraphs.^[43]

The reducible flow graphs are another class of directed graphs on which the feedback arc set problem may be solved in polynomial time. These graphs describe the flow of control in structured programs for many programming languages. Although structured programs often produce planar directed flow graphs, the definition of reducibility does not require the graph to be planar.^[44]

When the minimum feedback arc set problem is restricted to

derandomize the resulting algorithm using walks on expander graphs.^[34][46]

Hardness

NP-hardness

In order to apply the theory of

decision version

, with a yes or no answer (is it possible to remove ${\displaystyle k}$ edges). Thus, the decision version of the feedback arc set problem takes as input both a directed graph and a number ${\displaystyle k}$. It asks whether all cycles can be broken by removing at most ${\displaystyle k}$ edges, or equivalently whether there is an acyclic subgraph with at least ${\displaystyle |E(G)|-k}$ edges. This problem is

vertex cover problem, could be transformed ("reduced") into equivalent inputs to the feedback arc set decision problem.^[47][48]

Some NP-complete problems can become easier when their inputs are restricted to special cases. But for the most important special case of the feedback arc set problem, the case of tournaments, the problem remains NP-complete.[49]^[50]

Inapproximability

The complexity class

P = NP, it has no polynomial time approximation ratio better than 1.3606. This is the same threshold for hardness of approximation that is known for vertex cover, and the proof uses the Karp–Lawler reduction from vertex cover to feedback arc set, which preserves the quality of approximations.^{[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.^[38]

The hardness of approximation of these problems has also been studied under unproven computational hardness assumptions that are standard in computational complexity theory but stronger than P ≠ NP. 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 ${\displaystyle {\tfrac {1}{2}}+\varepsilon }$, for every ${\displaystyle \varepsilon >0}$.^[54] Beyond polynomial time for approximation algorithms, if the exponential time hypothesis is true, then for every ${\displaystyle \varepsilon >0}$ the minimum feedback arc set does not have an approximation within a factor ${\displaystyle {\tfrac {7}{6}}-\varepsilon }$ that can be computed in the subexponential time bound ${\displaystyle O(2^{n^{1-\varepsilon }})}$.^[55]

Theory

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.^[41][56] This is not true for some other graphs; for instance the first illustration shows a directed version of the non-planar graph ${\displaystyle K_{3,3}}$ in which the minimum size of a feedback arc set is two, while the maximum number of edge-disjoint directed cycles is only one.

Every tournament graph has a Hamiltonian path, and the Hamiltonian paths correspond one-for-one with minimal feedback arc sets, disjoint from the corresponding path. The Hamiltonian path for a feedback arc set is found by reversing its arcs and finding a topological order of the resulting acyclic tournament. Every consecutive pair of the order must be disjoint from the feedback arc sets, because otherwise one could find a smaller feedback arc set by reversing that pair. Therefore, this ordering gives a path through arcs of the original tournament, covering all vertices. Conversely, from any Hamiltonian path, the set of edges that connect later vertices in the path to earlier ones forms a feedback arc set. It is minimal, because each of its edges belongs to a cycle with the Hamiltonian path edges that is disjoint from all other such cycles.^[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. More precisely, every tournament graph has a feedback arc set of size ${\displaystyle {\tbinom {n}{2}}/2-\Omega (n^{3/2})}$, and some tournaments require size ${\displaystyle {\tbinom {n}{2}}/2-O(n^{3/2})}$.^[58] For almost all tournaments, the size is at least ${\displaystyle {\tbinom {n}{2}}/2-1.73n^{3/2}}$.^[59] Every directed acyclic graph ${\displaystyle D}$ can be embedded as a subgraph of a larger tournament graph, in such a way that ${\displaystyle D}$ is the unique minimum feedback arc set of the tournament. The size of this tournament has been defined as the "reversing number" of ${\displaystyle D}$, and among directed acyclic graphs with the same number of vertices it is largest when ${\displaystyle D}$ is itself an (acyclic) tournament.^[60][61]

A directed graph has an

strongly connected

and each vertex has equal numbers of incoming and outgoing edges. For such a graph, with ${\displaystyle m}$ edges and ${\displaystyle n}$ vertices, the size of a minimum feedback arc set is always at least ${\displaystyle (m^{2}+mn)/2n^{2}}$. There are infinitely many Eulerian directed graphs for which this bound is tight.^[62] If a directed graph has ${\displaystyle n}$ vertices, with at most three edges per vertex, then it has a feedback arc set of at most ${\displaystyle n/3}$ edges, and some graphs require this many. If a directed graph has ${\displaystyle m}$ edges, with at most four edges per vertex, then it has a feedback arc set of at most ${\displaystyle m/3}$ edges, and some graphs require this many.^[63]

References

1. ^ "Main draw – Men", Rio 2016, Fédération Internationale de Volleyball, archived from the original on 2016-12-23, retrieved 2021-11-14
2. ^
   MR 0429180
3. ^
   PMID 5964054
4. MR 0809110
   ; note that the algorithm suggested by Goddard for finding minimum-violation rankings is incorrect
5. S2CID 51887586
6. S2CID 18416
7. S2CID 54284406
8. doi:10.1016/0168-1591(93)90137-e
9. S2CID 203898549
10. JSTOR 2332752
11. MR 0115242
12. MR 0161419
13. JSTOR 20026529
14. ^
    S2CID 16512997
15. ^
    hdl:1721.1/4763
16. PMID 21068927
17. ^ Rosen, Edward M.; Henley, Ernest J. (Summer 1968), "The New Stoichiometry", Chemical Engineering Education, 2 (3): 120–125, archived from the original on 2021-08-02, retrieved 2021-08-02
18. ISBN 978-0-13-301615-4
19. doi:10.1007/3-540-44969-8_5
20. MR 2027115
21. ^
    S2CID 2437790
22. ^
    S2CID 5284738
23. MR 2045215
24. ^
    S2CID 18394348
25. S2CID 122603659
26. ^
    S2CID 207632524
27. doi:10.1109/tct.1963.1082116
28. doi:10.1109/tct.1964.1082291
29. ^
    S2CID 9967521
30. S2CID 1547510
31. S2CID 8008855
32. MR 0994519
33. MR 1881280
34. ^ ^{a b c} Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", A compendium of NP optimization problems, archived from the original on 2021-07-29, retrieved 2021-07-29
35. MR 1256786, archived
    from the original on 2020-10-22, retrieved 2021-08-01
36. MR 1474592
37. MR 1290207
38. ^
    hdl:1721.1/86548, as cited by Guruswami et al. (2011)
39. ^
    MR 1334365
40. ^
    S2CID 27825518
41. ^
    MR 0500618
42. ^
    S2CID 32162097
43. S2CID 206798683
44. MR 0955140
45. S2CID 9436948, ECCC TR06-144; see also author's extended version Archived 2009-01-15 at the Wayback Machine
46. S2CID 3207086, archived
    from the original on 2021-08-03, retrieved 2021-08-03
47. ^ Karp, Richard M. (1972), "Reducibility among combinatorial problems", Complexity of Computer Computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., New York: Plenum, pp. 85–103
48. ISBN 0-7167-1045-5
49. MR 2257251
50. S2CID 36539840
51. MR 0589808
52. ^ Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF) (Ph.D. thesis), Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, archived (PDF) from the original on 2010-12-29, retrieved 2007-10-11
53. S2CID 1235048
54. MR 2823511, archived
    (PDF) from the original on 2021-07-31, retrieved 2021-07-31
55. S2CID 3136275
56. MR 0427138
57. MR 1033709
58. S2CID 119894999
59. MR 0735201
60. MR 1339075
61. MR 2095357
62. S2CID 7967738
63. MR 3139198