Feedback Edge/Vertex Set

  

 

Input description: A (directed) graph G=(V,E).

Problem description: What is the smallest set of edges E' or vertices V' whose deletion leaves an acyclic graph?

Discussion: Feedback set problems arise because many algorithmic problems are much easier or much better defined on directed acyclic graphs than on arbitrary digraphs.   Topological sorting (see Section ) can be used to test whether a graph is a DAG, and if so, to order the vertices so as to respect the edges as precedence scheduling constraints.     But how can you design a schedule if there are cyclic constraints, such as A must be done before B, which must be done before C, which must be done before A?

By identifying a feedback set, we identify the smallest number of constraints that must be dropped so as to permit a valid schedule.   In the feedback edge (or arc) set problem, we drop precedence constraints (job A must come before job B). In the feedback vertex set problem, we drop entire jobs and any associated constraints. It is also referred to in the literature as the maximum acyclic subgraph problem.    

• Do any constraints have to be dropped? - Not if the graph is a DAG, which can be tested via topological sort in linear time, Further, topological sorting also gives a simple way to find a feedback set if we modify the algorithm to delete the edge or vertex whenever a contradiction is found instead of simply printing a warning. The catch is that this feedback set might be much larger than needed, no surprise since both feedback edge set and feedback vertex set are NP-complete on directed graphs.
• How can I find a good feedback edge set? - A simple but effective linear-time heuristic constructs a vertex ordering, just as in the topological sort heuristic above, and deletes any arc going from right to left. This heuristic builds up the ordering from the outside in based on the in- and out-degrees of each vertex. Any vertex of in-degree 0 is a source and can be placed first in the ordering. Any vertex of out-degree 0 is a sink and can be placed last in the ordering, again without violating any constraints. If not, we find the vertex with the maximum difference between in- and out-degree, and place it on the side of the permutation that will salvage the greatest number of constraints. Delete any vertex from the DAG after positioning it and repeat until the graph is empty.
• How can I find a good feedback vertex set? - The following variant of the above heuristic should be effective. Keep any source or sink we encounter. If none exist, add to the feedback set a vertex v that maximizes , since this vertex is furthest from becoming either a source or sink. Again, delete any vertex from the DAG after positioning it and repeat until the graph is empty.
• What if I want to break all cycles in an undirected graph? - The problem of finding feedback sets from undirected graphs is different for digraphs, and in one case actually easier.   An undirected graph without cycles is a tree.   It is well known that any tree on n vertices has exactly n-1 edges. Thus the smallest feedback edge set of any undirected graph is |E| - (n-1), and it can be found by deleting all the edges not in any given spanning tree. Spanning trees can be most efficiently constructed using depth-first search, as discussed in Section . The feedback vertex set problem remains NP-complete for undirected graphs, however.

Finding an optimal feedback set is NP-complete, and for most applications it is unlikely to be worth searching for the smallest set. However, in certain applications it would pay to try to refine the heuristic solutions above via randomization or simulated annealing.   To move between states, we modify the vertex permutation by swapping pairs in order or inserting/deleting vertices into the feedback set.

Implementations: The econ_order program of the Stanford GraphBase (see Section )   permutes the rows and columns of a matrix so as to minimize the sum of the numbers below the main diagonal.   Using an adjacency matrix as the input and deleting all edges below the main diagonal leaves an acyclic graph.

Notes: The feedback set problem first arose in [Sla61]. Heuristics for feedback set problems include [BYGNR94, ELS93, Fuj96]. Expositions of the proofs that feedback minimization is hard [Kar72] include [AHU74, Eve79a]. Both feedback vertex and edge set remain hard even if no vertex has in-degree or out-degree greater than two [GJ79].

An interesting application of feedback arc set to economics is presented in [Knu94]. For each pair A,B of sectors of the economy, we are given how much money flows from A to B. We seek to order the sectors to determine which sectors are primarily producers to other sectors, and which deliver primarily to consumers.  

Related Problems: Bandwidth reduction (see page ), topological sorting (see page ), scheduling (see page ).