{"ID":22952805,"CreatedAt":"2026-09-17T02:12:05.498442134Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19129","arxiv_id":"2609.19129","title":"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.","short_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...","url_abs":"https://arxiv.org/abs/2609.19129","url_pdf":"https://arxiv.org/pdf/2609.19129v1","authors":"[\"Sounak Modak\"]","published":"2026-09-16T17:51:01Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}