Reducibility
Glossary Contents
← Ch VII
Chapter VIII Feedback Arc Set
Ch IX →
  1. 22 — The wrong-way edges
  2. 23 — Eades–Lin–Smyth in Rust
  3. 24 — Ranking the unrankable
24

Ranking the unrankable

Whenever you have to fuse contradictory rankings — sports tournaments, search results, peer reviews — you are computing a feedback arc set.

Premier League tables, Elo chess ratings, Google's pre-PageRank ranking experiments, and Yelp's reviewer-merging problem are all instances of rank aggregation. Each input ranker (or pairwise game) gives a directed edge "A beats B." Some triangles say A>B, B>C, C>A — Condorcet's paradox in graph form. The minimum number of edges to remove to get a consistent linear order is exactly minimum FAS. In academic peer review, NeurIPS aggregates conflicting reviewer scores via approximate FAS solvers. In package managers (npm, Cargo), the dependency upgrade graph occasionally has cycles you have to break — picking which constraint edges to relax is FAS over the constraint graph. And FAS shows up in VLSI placement: edge-crossings in a hierarchical layout are minimized by laying nodes on layers and minimizing back-edges.

In plain terms

When ten reviewers disagree about which of fifty papers is best, no ranking will make all of them happy. The "best" ranking is the one with fewest disagreements — fewest pairs of papers ordered opposite to what reviewers said. That count is the minimum feedback arc set.

Scan to come back to page 24

End of Chapter VIII
Chapter IX Directed Hamilton Circuit →
← 23 Eades–Lin–Smyth in Rust
3/3 · 24/63
25 Visit every node, exactly once →