The problem
Three arrows A to B, B to C and C to A form a loop. If removing A costs one unit, B four and C seven, removing A breaks the loop most cheaply. Can an efficient deterministic algorithm always break every directed loop at a cost within one fixed multiple of the cheapest possible, for any arrow network?[1]
Can every arrow network be made free of directed cycles at a reliably bounded cost, without solving its minimum-cost removal problem exactly? In the three-cycle A→B→C→A with weights 1,4,7, removing A costs 1 and is optimal: some vertex must be removed, and A is cheapest.
For arbitrary finite digraph D and nonnegative rational weights w, seek one universal C and a deterministic algorithm polynomial in the full input encoding. It must return a vertex set F with D−F acyclic and . The factor cannot grow with graph size, and the encoding includes the bits needed to specify the weights.[1] [2]
Scope
Arbitrary finite directed graphs with nonnegative rational vertex weights. The algorithm must return vertices whose deletion leaves no directed cycle.
What remains open
Fixed-ratio methods are available for specially structured arrow networks; a recent preprint gives randomized improvements in such classes. The unrestricted deterministic guarantee is still missing. A conjectured complexity assumption would rule it out, but that assumption is not an unconditional impossibility proof.[1] [2]
The July 2026 quasi-transitive theorem and September structured-class preprint do not imply a constant ratio for general digraphs.[2]
Why it matters
Once every arrow loop is broken, the surviving vertices can be listed so that each arrow goes forward. A single removed vertex may break several loops, so treating each loop separately can discard far more than necessary. Controlling that loss links the removal problem to how an entangled collection of cyclic dependencies can be turned into an ordered one.[2]
An undirected triangle is cyclic, yet directing its edges from earlier to later vertices removes every directed cycle without deleting a vertex. Orientation therefore changes which obstructions need to be hit. A factor-two approximation is known for undirected cycle removal, while a general directed constant factor is ruled out if the Unique Games Conjecture holds. The contrast asks which structural information makes controlled-cost restoration of an acyclic graph possible, beyond the directed families already admitting fixed factors.[1]
Definitions
Sources
- A 9/4-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs
Notes on A 9/4-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs
Introduction states the general approximation gap and conditional Unique Games hardness; its theorem restricts the graph class.
- A 2-Approximation for Directed Feedback Vertex Set in Locally Semicomplete and Quasi-Transitive Digraphs
Notes on A 2-Approximation for Directed Feedback Vertex Set in Locally Semicomplete and Quasi-Transitive Digraphs
Preprint reports randomized guarantees on structured digraphs and retains the general conditional hardness boundary.