arXiv preprint ·
A deterministic $(2 + \varepsilon)$-approximation for directed feedback vertex sets in tournaments
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
High-Performance Tensor Formulation of the Viterbi Algorithm for Hidden Semi-Markov Models
A quantitative tree-likeness bound from average hyperbolicity
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
The Price of Random Access: Measuring Block Granularity Across Four Compressed Formats
Serial-batch scheduling to minimise the total weighted late work
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.