Approximate algorithms cut cycles in complex directed graphs efficiently
A $2$-Approximation for Directed Feedback Vertex Set in Locally Semicomplete and Quasi-Transitive Digraphs
Data Structures and Algorithms
Summary
The problem of removing the smallest number of points to break all loops in a directed network is important for many tasks but hard to solve exactly. The authors extended a known method that works well for special networks called tournaments to two more general types of networks called locally semicomplete and quasi-transitive digraphs. Their approach guarantees a solution within twice the minimal size and runs efficiently with some randomness. This improves previous results and is optimal assuming a widely believed computational hypothesis.
What this means in practice
- •For network engineers: Remove minimal nodes to prevent feedback loops in communication or control networks modeled by complex directed graphs.
- •For software engineers: Optimize software dependency graphs by efficiently identifying minimal sets of modules to remove to eliminate cyclic dependencies.
Authors
Sounak Modak
Abstract
A \emph{directed feedback vertex set} of a digraph is a set of vertices whose removal destroys all directed cycles. The \textsc{Directed Feedback Vertex Set} (\textsc{DFVS}) problem asks for such a set of minimum cardinality or minimum total weight. Although general \textsc{DFVS} admits no constant-factor approximation under the {Unique Games Conjecture}, tournaments admit a randomized factor-$2$ approximation due to Lokshtanov et al. [SODA'20]. We extend this guarantee to two broader classes of structured digraphs, both of which also contain sparse digraphs. Our first and main result is a randomized polynomial-time factor-$2$ approximation for weighted \textsc{DFVS} on \emph{locally semicomplete digraphs} (\textsf{LSD}s), a class that strictly generalizes semicomplete digraphs and tournaments. To the best of our knowledge, this is the first non-trivial constant-factor approximation for \textsc{DFVS} on \textsf{LSD}s, even in the unweighted setting. Our second result is a randomized polynomial-time factor-$2$ approximation for weighted \textsc{DFVS} on \emph{quasi-transitive digraphs}, improving the recent deterministic $9/4$-approximation of Ghorbani and Mnich~[ICALP'26]. The algorithm follows from a simple recursive application of our composition framework. The factor $2$ is optimal under the {Unique Games Conjecture}, since tournaments are subclass of \textsf{LSD}s as well as quasi-transitive digraphs.