next up previous contents index CD CD Algorithms
Next: Computational Geometry Up: Graph Problems: Hard Problems Previous: Steiner Tree

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 gif) 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.    

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 gif)   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 gif), topological sorting (see page gif), scheduling (see page gif).      

next up previous contents index CD CD Algorithms
Next: Computational Geometry Up: Graph Problems: Hard Problems Previous: Steiner Tree

Mon Jun 2 23:33:50 EDT 1997