A $2$-Approximation for Directed Feedback Vertex Set in Locally Semicomplete and Quasi-Transitive Digraphs

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.