Chapter VIII Feedback Arc Set

The wrong-way edges

Lay the vertices on a line, count the edges going backwards. Find the line that minimizes that count.

A feedback arc set is a set of edges whose removal leaves a directed graph acyclic:

A \subseteq E such that (V, E ∖ A) is a DAG. (1)

Equivalently, the minimum set satisfying (1) is the minimum count of back-edges under any linear ordering of the vertices:

A : (1) holds min ∣ A ∣ = σ \in S_{n} min {(u, v) \in E : σ (u) > σ (v)} . (2)

The identity (2) is the reason FAS shows up under another name — rank aggregation — when the input is a tournament. NP-hard in general (Karp), but a constant-factor approximation is achievable, and several near-linear heuristics (Eades–Lin–Smyth) work shockingly well in practice.

Figures, in plain terms

(1)

A ⊆ E picks a subset of edges (not vertices, like in the previous chapter) to remove.

E \ A is set difference — the edges of E that are not in A.

The notation (V, E \ A) rebuilds the graph with the same vertices but the trimmed edge set.

The condition is a DAG stands for "directed acyclic graph" — a graph with no directed cycles. So removing A clears every cycle.

(2)

Two new symbols here. σ (Greek sigma) is a permutation of the n vertices — a particular ordering, lining the dots up left to right.

S_n is the symmetric group of all permutations on n items. So min over σ ∈ S_n asks: across every possible ordering, find the one with...

The right side counts edges going backward in the chosen order. σ(u) > σ(v) means u sits to the right of v in the ordering, but the edge points from u to v — pointing backward. The vertical bars |...| count those edges.

The whole identity says: the minimum FAS size equals the minimum back-edge count, taken over all orderings of the vertices. A ranking with few back-edges is exactly a small feedback arc set.