Ghorbani, EbrahimEbrahimGhorbaniMnich, MatthiasMatthiasMnich2026-07-022026-07-022026-0753rd International Colloquium on Automata, Languages, and Programming, ICALP 2026https://hdl.handle.net/11420/63773We 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).enhttps://creativecommons.org/licenses/by/4.0/directed feedback vertex settournamentsquasi-transitive digraphsNatural Sciences and Mathematics::510: MathematicsContribution to Conferencehttps://doi.org/10.15480/882.1741410.4230/LIPIcs.ICALP.2026.9610.15480/882.17414