2026-09-08T01:22:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26485 2026-09-05T19:45:13Z ddc:004 open_access

A 9/4-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs Ghorbani, Ebrahim Mnich, Matthias directed feedback vertex set tournaments quasi-transitive digraphs We provide the first non-trivial approximation algorithm for the fundamental directed feedback vertex set (DFVS) problem in the class of quasi-transitive digraphs. This class of digraphs encompasses both dense and sparse classes of digraphs, for which specialized DFVS algorithms were proposed in the literature, like tournaments or transitive orientations of bounded treewidth graphs. Our approximation algorithm can handle both dense graphs, as well as sparse graphs, by a single approach, which is based on carefully analysing the solutions to a linear programming relaxation of DFVS. It also handles the node-weighted DFVS problem, for which it computes a 9/4-approximation in polynomial time. Along the way, we improve and simplify the best-known deterministic polynomial-time approximation algorithms for DFVS in tournaments (Cai et al., SICOMP 2001; Mnich et al., ESA 2016). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ebrahim Ghorbani and Matthias Mnich 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.96 urn:nbn:de:0030-drops-264852 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.96 eng https://creativecommons.org/licenses/by/4.0/legalcode