Feedback arc set

The minimum feedback arc set and maximum acyclic subgraph are equivalent for the purposes of exact optimization, as one is the complement set of the other. However, for parameterized complexity and approximation, they differ, because the analysis used for those kinds of algorithms depends on the size of the solution and not just on the size of the input graph, and the minimum feedback arc set and maximum acyclic subgraph have different sizes from each other.[23]

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]

A directed graph with three strongly connected components, the rightmost of which can be split at articulation vertex ${\displaystyle d}$ 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.

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]

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 polynomial space.[29]

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 linear time.[32] All minimal feedback arc sets can be listed by an algorithm with polynomial delay per set.[33]

The best known polynomial-time approximation algorithm for the feedback arc set has the non-constant approximation ratio ${\displaystyle O(\log n\log \log n)}$. 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.[34]

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]

In directed planar graphs, the feedback arc set problem is dual to the problem of contracting a set of edges (a dijoin) to make the resulting graph strongly connected.[39] This dual problem is polynomially solvable,[40] and therefore the planar minimum feedback arc set problem is as well.[41][40] It can be solved in time ${\displaystyle O(n^{5/2}\log n)}$.[42] A weighted version of the problem can be solved in time ${\displaystyle O(n^{3})}$,[39] or when the weights are positive integers that are at most a number ${\displaystyle N}$, in time ${\displaystyle O(n^{5/2}\log nN)}$.[42] These planar algorithms can be extended to the graphs that do not have the 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 tournaments, it has a polynomial-time approximation scheme, which generalizes to a weighted version of the problem.[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]

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.

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 ${\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 NP-complete, implying that neither it nor the optimization problem are expected to have polynomial time algorithms. It was one of Richard M. Karp's original set of 21 NP-complete problems; its NP-completeness was proved by Karp and Eugene Lawler by showing that inputs for another hard problem, the 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]

The complexity class APX is defined as consisting of optimization problems that have a polynomial time approximation algorithm that achieves a constant approximation ratio. Although such approximations are not known for the feedback arc set problem, the problem is known to be APX-hard, meaning that accurate approximations for it could be used to achieve similarly accurate approximations for all other problems in APX. As a consequence of its hardness proof, unless 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]