Options
A 9/4-approximation for directed feedback vertex sets in quasi-transitive igraphs
Citation Link: https://doi.org/10.15480/882.17414
Publikationstyp
Contribution to Conference
Date Issued
2026-07
Sprache
English
TORE-DOI
Citation
53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)
Contribution to Conference
Publisher DOI
Peer Reviewed
true
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).
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).
Subjects
directed feedback vertex set
tournaments
quasi-transitive digraphs
DDC Class
510: Mathematics
Publication version
publishedVersion
Loading...
Name
LIPIcs.ICALP.2026.96.pdf
Size
923.1 KB
Format
Adobe PDF