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

A \emph{directed feedback vertex set} of a digraph is a set of vertices whose removal destroys all directed cycles. The $\text{textsc}DirectedFeedbackVertexSet$ ($\text{textsc}DFVS$) problem asks for such a set of minimum cardinality or minimum total weight. Although general $\text{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 $\text{textsc}DFVS$ on \emph{locally semicomplete digraphs} ($\mathsf{\text{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 $\text{textsc}DFVS$ on $\mathsf{\text{LSD}}$s, even in the unweighted setting. Our second result is a randomized polynomial-time factor-$2$ approximation for weighted $\text{textsc}DFVS$ on \emph{quasi-transitive digraphs}, improving the recent deterministic $9\mathrm{/}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 $\mathsf{\text{LSD}}$s as well as quasi-transitive digraphs.