HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
and
graph algorithm An algorithm is fundamentally a set of rules or defined procedures that is typically designed and used to solve a specific problem or a broad set of problems. Broadly, algorithms define process(es), sets of rules, or methodologies that are to be f ...
s, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
. 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 problem In mathematics, engineering, computer science and economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
s 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 Chemical engineering is an engineering field which deals with the study of the operation and design of chemical plants as well as methods of improving production. Chemical engineers develop economical commercial processes to convert raw materials ...
,
deadlock Deadlock commonly refers to: * Deadlock (computer science), a situation where two processes are each waiting for the other to finish * Deadlock (locksmithing) or deadbolt, a physical door locking mechanism * Political deadlock or gridlock, a si ...
resolution,
ranked voting Ranked voting is any voting system that uses voters' Ordinal utility, rankings of candidates to choose a single winner or multiple winners. More formally, a ranked vote system depends only on voters' total order, order of preference of the cand ...
, ranking competitors in sporting events,
mathematical psychology Mathematical psychology is an approach to psychology, psychological research that is based on mathematical modeling of perceptual, thought, Cognition, cognitive and motor processes, and on the establishment of law-like rules that relate quantifi ...
,
ethology Ethology is a branch of zoology that studies the behavior, behaviour of non-human animals. It has its scientific roots in the work of Charles Darwin and of American and German ornithology, ornithologists of the late 19th and early 20th cen ...
, and
graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such ...
. Finding minimum feedback arc sets and maximum acyclic subgraphs is
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
; it can be solved exactly in
exponential time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
, or in
fixed-parameter tractable In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
time. In
polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
, the minimum feedback arc set can be approximated to within a polylogarithmic
approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
, and maximum acyclic subgraphs can be approximated to within a constant factor. Both are hard to approximate closer than some constant factor, an
inapproximability In computer science, hardness of approximation is a field that studies the Computational complexity theory, algorithmic complexity of finding near-optimal solutions to optimization problems. Scope Hardness of approximation complements the study of ...
result that can be strengthened under the
unique games conjecture In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of g ...
. For tournament graphs, the minimum feedback arc set can be approximated more accurately, and for
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s both problems can be solved exactly in polynomial time. A closely related problem, the feedback vertex set, is a set of vertices containing at least one vertex from every cycle in a directed or undirected graph. In
undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...
s, the
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
s are the largest acyclic subgraphs, and the number of edges removed in forming a spanning tree is the
circuit rank In graph theory, a branch of mathematics, the cyclomatic number, circuit rank, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...
.


Applications

Several problems involving rankings or orderings can be solved by finding a feedback arc set on a tournament graph, a directed graph with one edge between each pair of vertices. Reversing the edges of the feedback arc set produces a
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
whose unique
topological order In physics, topological order describes a state or phase of matter that arises system with non-local interactions, such as entanglement in quantum mechanics, and floppy modes in elastic systems. Whereas classical phases of matter such as gases an ...
can be used as the desired ranking. Applications of this method include the following: *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. Many sports use simpler methods for
group tournament ranking system In a group tournament, unlike a knockout tournament, there is no scheduled decisive final match. Instead, all the competitors are ranked by examining the results of all the matches played in the tournament. Typically, points are awarded for eac ...
s based on points awarded for each game; these methods can provide a constant approximation to the minimum-upset ranking. *In
primatology Primatology is the scientific study of non-human primates. It is a diverse discipline at the boundary between mammalogy and anthropology, and researchers can be found in academic departments of anatomy, anthropology, biology, medicine, psychol ...
and more generally in
ethology Ethology is a branch of zoology that studies the behavior, behaviour of non-human animals. It has its scientific roots in the work of Charles Darwin and of American and German ornithology, ornithologists of the late 19th and early 20th cen ...
,
dominance hierarchies In the zoological field of ethology, a dominance hierarchy (formerly and colloquially called a pecking order) is a type of social hierarchy that arises when members of animal social groups interact, creating a ranking system. Different types of ...
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. *In
mathematical psychology Mathematical psychology is an approach to psychology, psychological research that is based on mathematical modeling of perceptual, thought, Cognition, cognitive and motor processes, and on the establishment of law-like rules that relate quantifi ...
, 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. Alternatively, if these comparisons result in independent probabilities for each pairwise ordering, then the
maximum likelihood estimation In statistics, maximum likelihood estimation (MLE) is a method of estimation theory, estimating the Statistical parameter, parameters of an assumed probability distribution, given some observed data. This is achieved by Mathematical optimization, ...
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. *The same maximum-likelihood ordering can be used for seriation, the problem in
statistics Statistics (from German language, German: ', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a s ...
and
exploratory data analysis In statistics, exploratory data analysis (EDA) is an approach of data analysis, analyzing data sets to summarize their main characteristics, often using statistical graphics and other data visualization methods. A statistical model can be used or ...
of arranging elements into a linear ordering, in cases where data is available that provides pairwise comparisons between the elements. *In
ranked voting Ranked voting is any voting system that uses voters' Ordinal utility, rankings of candidates to choose a single winner or multiple winners. More formally, a ranked vote system depends only on voters' total order, order of preference of the cand ...
, the
Kemeny–Young method The Kemeny–Young method is an electoral system that uses ranked ballots and pairwise comparison counts to identify the most popular choices in an election. It is a Condorcet method because if there is a Condorcet winner, it will always be ran ...
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. 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. Another early application of feedback arc sets concerned the design of
sequential logic In automata theory, sequential logic is a type of logic circuit whose output depends on the present value of its input signals and on the sequence of past inputs, the input history. This is in contrast to '' combinational logic'', whose output i ...
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. In
synchronous circuit In digital electronics, a synchronous circuit is a digital circuit in which the changes in the state (computer science), state of memory elements are synchronized by a clock signal. In a sequential logic, sequential digital logic circuit, data ...
s made from asynchronous components, synchronization can be achieved by placing clocked gates on the edges of a feedback arc set. Additionally, cutting a circuit on a feedback arc a set reduces the remaining circuit to
combinational logic In automata theory, combinational logic (also referred to as time-independent logic) is a type of digital logic that is implemented by Boolean circuits, where the output is a pure function of the present input only. This is in contrast to sequ ...
, 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. Similarly, in process flowsheeting in
chemical engineering Chemical engineering is an engineering field which deals with the study of the operation and design of chemical plants as well as methods of improving production. Chemical engineers develop economical commercial processes to convert raw materials ...
, breaking edges of a
process flow diagram A process flow diagram (PFD) is a diagram commonly used in chemical and process engineering to indicate the general flow of plant processes and equipment. The PFD displays the relationship between ''major'' equipment of a plant facility and does ...
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". In
layered graph drawing Layered graph drawing or hierarchical 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.... It is also known as Sugiyama-style gr ...
, 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. Feedback arc sets have also been used for a different subproblem of layered graph drawing, the ordering of vertices within consecutive pairs of layers. In
deadlock Deadlock commonly refers to: * Deadlock (computer science), a situation where two processes are each waiting for the other to finish * Deadlock (locksmithing) or deadbolt, a physical door locking mechanism * Political deadlock or gridlock, a si ...
resolution in
operating system An operating system (OS) is system software that manages computer hardware and software resources, and provides common daemon (computing), services for computer programs. Time-sharing operating systems scheduler (computing), schedule tasks for ...
s, 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. 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.


Algorithms


Equivalences

The minimum feedback arc set and maximum acyclic subgraph are equivalent for the purposes of exact optimization, as one is the
complement set In set theory, the complement of a set , often denoted by A^c (or ), is the set of elements not in . When all elements in the universe, i.e. all elements under consideration, are considered to be members of a given set , the absolute complement ...
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. A feedback arc set of a given graph G is the same as a feedback vertex set of a directed
line graph In the mathematics, mathematical discipline of graph theory, the line graph of an undirected graph is another graph that represents the adjacencies between edge (graph theory), edges of . is constructed in the following way: for each edge i ...
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 G has a vertex for each edge and an edge for each two-edge path In the other direction, the minimum feedback vertex set of a given graph G can be obtained from the solution to a minimum feedback arc set problem on a graph obtained by splitting every vertex of 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. In both exact and approximate solutions to the feedback arc set problem, it is sufficient to solve separately each
strongly connected component In the mathematics, mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachability, reachable from every other vertex. The strongly connected components of a directed graph form a partition of a s ...
of the given graph, and to break these strongly connected components down even farther to their
biconnected component In graph theory, a biconnected component or block (sometimes known as a 2-connected component) is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. Th ...
s 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. 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.


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. Searching all
permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...
s of an graph would take but a dynamic programming method based on the Held–Karp algorithm can find the optimal permutation in also using an exponential amount of space. A
divide-and-conquer algorithm In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved dir ...
that tests all partitions of the vertices into two equal subsets and recurses within each subset can solve the problem in using polynomial space. In
parameterized complexity In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
, 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 n vertices, with natural the feedback arc set problem can be solved in by transforming it into an equivalent feedback vertex set problem and applying a parameterized feedback vertex set algorithm. Because the exponent of n in this algorithm is the independent this algorithm is said to be fixed-parameter tractable. 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 where r is the
circuit rank In graph theory, a branch of mathematics, the cyclomatic number, circuit rank, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or fo ...
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 connected graph to reduce it to a
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...
; it is much easier to compute than the minimum feedback arc set. For graphs of 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 Under the exponential time hypothesis, no better dependence on t is possible. 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 In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations ...
. All minimal feedback arc sets can be listed by an algorithm with polynomial delay per set.


Approximate

The best known polynomial-time approximation algorithm for the feedback arc set has the non-constant
approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
This means that the size of the feedback arc set that it finds is at most this factor larger than the optimum. Determining whether feedback arc set has a constant-ratio approximation algorithm, or whether a non-constant ratio is necessary, remains an open problem. The maximum acyclic subgraph problem has an easy approximation algorithm that achieves an approximation ratio *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 A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
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 m edges and n vertices, this produces an acyclic subgraph with m/2+n/6 edges, in linear time, giving an approximation ratio Another, more complicated, polynomial–time approximation algorithm applies to graphs with maximum and finds an acyclic subgraph with m/2+\Omega(m/\sqrt) edges, giving an approximation ratio of the When \Delta=3, the approximation ratio 8/9 can be achieved.


Restricted inputs

In directed
planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...
s, 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 In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are thems ...
. This dual problem is polynomially solvable, and therefore the planar minimum feedback arc set problem is as well. It can be solved in A weighted version of the problem can be solved in or when the weights are positive integers that are at most a in These planar algorithms can be extended to the graphs that do not have the
utility graph In economics, utility is a measure of a certain person's satisfaction from a certain state of the world. Over time, the term has been used with at least two meanings. * In a normative context, utility refers to a goal or objective that we wish ...
K_ as a
graph minor In graph theory, an undirected graph is called a minor of the graph if can be formed from by deleting edges, vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if ...
, using the fact that the triconnected components of these graphs are either planar or of bounded size. Planar graphs have also been generalized in a different way to a class of directed graphs called ''weakly acyclic digraphs'', defined by the
integrality In commutative algebra, an element ''b'' of a commutative ring ''B'' is said to be integral over a subring ''A'' of ''B'' if ''b'' is a root of some monic polynomial over ''A''. If ''A'', ''B'' are fields, then the notions of "integral over" and ...
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. 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. When the minimum feedback arc set problem is restricted to
tournaments A tournament is a competition involving at least three competitors, all participating in a sport or game. More specifically, the term may be used in either of two overlapping senses: # One or more competitions held at a single venue and concentr ...
, it has a
polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an inst ...
, which generalizes to a weighted version of the problem. A subexponential parameterized algorithm for weighted feedback arc sets on tournaments is also known. The maximum acyclic subgraph problem for
dense graph In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected by one edge). The opposite, a graph with only a few edges, is a sparse graph. The distinctio ...
s also has a polynomial-time approximation scheme. Its main ideas are to apply
randomized rounding In computer science and operations research, randomized rounding is a widely used approach for designing and analyzing approximation algorithms. Many combinatorial optimization problems are computationally intractability (complexity), intrac ...
to a
linear programming relaxation In mathematics, the relaxation of a (mixed) integer linear program is the problem that arises by removing the integrality constraint of each variable. For example, in a 0–1 integer program, all constraints are of the form :x_i\in\. The rela ...
of the problem, and to derandomize the resulting algorithm using walks on
expander graph In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several appli ...
s.


Hardness


NP-hardness

In order to apply the theory of
NP-completeness In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
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 k edges). Thus, the decision version of the feedback arc set problem takes as input both a directed graph and a It asks whether all cycles can be broken by removing at most k edges, or equivalently whether there is an acyclic subgraph with at least , E(G), -k edges. This problem is
NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
, 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 Eugene Leighton (Gene) Lawler (1933 – September 2, 1994) was an American computer scientist and a professor of computer science at the University of California, Berkeley... Reprinted in . Academic life Lawler came to Harvard as a graduate stu ...
by showing that inputs for another hard problem, the
vertex cover problem In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...
, could be transformed ("reduced") into equivalent inputs to the feedback arc set decision problem. 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.


Inapproximability

The complexity class APX is defined as consisting of optimization problems that have a polynomial time approximation algorithm that achieves a constant
approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
. Although such approximations are not known for the feedback arc set problem, the problem is known to be
APX-hard In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor a ...
, 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 The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved. Here, "quickly" means an algorithm exists that ...
, 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. 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. The hardness of approximation of these problems has also been studied under unproven
computational hardness assumption In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently (where ''efficiently'' typically means "in polynomial time"). It is not known how to prove (unconditi ...
s that are standard in computational complexity theory but stronger than P ≠ NP. If the
unique games conjecture In computational complexity theory, the unique games conjecture (often referred to as UGC) is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate ''value'' of a certain type of g ...
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 for Beyond polynomial time for approximation algorithms, if the exponential time hypothesis is true, then for every \varepsilon>0 the minimum feedback arc set does not have an approximation within a factor \tfrac76-\varepsilon that can be computed in the subexponential time bound


Theory

In planar directed graphs, the feedback arc set problem obeys a
min-max theorem In linear algebra and functional analysis, the min-max theorem, or variational theorem, or Courant–Fischer–Weyl min-max principle, is a result that gives a variational characterization of eigenvalues of compact Hermitian operators o ...
: the minimum size of a feedback arc set equals the maximum number of edge-disjoint directed cycles that can be found in the graph. This is not true for some other graphs; for instance the first illustration shows a directed version of the non-planar graph K_ 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 In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vert ...
, 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. 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 and some tournaments require size For
almost all In mathematics, the term "almost all" means "all but a negligible quantity". More precisely, if X is a set (mathematics), set, "almost all elements of X" means "all elements of X but those in a negligible set, negligible subset of X". The meaning o ...
tournaments, the size is at least Every
directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ...
D can be embedded as a subgraph of a larger tournament graph, in such a way that D is the unique minimum feedback arc set of the tournament. The size of this tournament has been defined as the "reversing number" and among directed acyclic graphs with the same number of vertices it is largest when D is itself an (acyclic) tournament. A directed graph has an
Euler tour In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and end ...
whenever it is
strongly connected In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of a directed graph form a partition into subgraphs that are thems ...
and each vertex has equal numbers of incoming and outgoing edges. For such a graph, with m edges and n vertices, the size of a minimum feedback arc set is always at least There are infinitely many Eulerian directed graphs for which this bound is tight. If a directed graph has n vertices, with at most three edges per vertex, then it has a feedback arc set of at most n/3 edges, and some graphs require this many. If a directed graph has m edges, with at most four edges per vertex, then it has a feedback arc set of at most m/3 edges, and some graphs require this many.


References

{{DEFAULTSORT:Feedback Arc Set Directed graphs Graph theory objects NP-complete problems Computational problems in graph theory