Metraipolis › archive › dc_f09f75233ab9

A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments — arXiv:2609.16723

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.16723
License (as archived)
CC0-1.0
Archived
2026-10-15T21:59:08.279Z
SHA-256 of the archived text
9085f75357b2fc0ffff896e4ef44a07c2e991a85b7681b4667c68f161601d0d6
Stable URL of this page
https://metraipolis.com/documento/dc_f09f75233ab9

How to cite

A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments — arXiv:2609.16723 — arXiv (en), https://arxiv.org/abs/2609.16723 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f09f75233ab9 (Metraipolis archive dc_f09f75233ab9, sha256 9085f75357b2fc0ffff896e4ef44a07c2e991a85b7681b4667c68f161601d0d6)
BibTeX
@misc{dcf09f75233ab9,
  title = {A deterministic $(2 + varepsilon)$-approximation for directed feedback vertex sets in tournaments — arXiv:2609.16723},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.16723},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f09f75233ab9; sha256 9085f75357b2fc0ffff896e4ef44a07c2e991a85b7681b4667c68f161601d0d6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.16723. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We nearly settle the polynomial-time approximability of the Directed Feedback Vertex Set problem in tournaments. This problem is Vertex Cover-hard, and thus cannot have a $(2 - \varepsilon)$-approximation for any $\varepsilon > 0$ in polynomial time assuming the Unique Games Conjecture. In the past 28 years, several works have attempted to attain this approximability barrier of 2, and have designed algorithms with smaller and smaller approximation factors. This includes a $5/2$-approximation by Cai, Deng and Zang (FOCS 1998, SICOMP 2001); a $7/3$-approximation by Mnich, Vassilevska Williams and V{é}gh (ESA 2016), another $7/3$-approximation by Aprile, Drescher, Fiorini and Huynh (DAM 2023), and a $9/4$-approximation by Ghorbani and Mnich (ICALP 2026). Our main result improves upon all of those works: we give the first deterministic polynomial-time $(2+\varepsilon)$-approximation for Directed Feedback Vertex Set in tournaments, for all $\varepsilon > 0$. We thereby almost answer an open question by Lokshtanov, Misra, Mukherjee, Panolan, Philip and Saurabh (SODA 2020) who asked for a deterministic 2-approximation in polynomial time. Furthermore, we extend our result to the broader class of quasi-transitive digraphs

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-16 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.16723 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T21:46:54.565Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-16?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).