Deterministic algorithm improves cycle-breaking in directed tournaments

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

Data Structures and Algorithms

Summary

The Directed Feedback Vertex Set problem asks how to remove the smallest set of nodes to eliminate all cycles in a directed graph, specifically in a tournament where each pair of nodes has one directed edge. This problem is known to be hard to solve exactly. The authors present a new deterministic algorithm that finds a solution within a factor of 2 plus any small margin, improving on previous algorithms with larger factors. Their method also works for a wider class of graphs called quasi-transitive digraphs. This nearly matches theoretical limits on how well this problem can be approximated efficiently.

What this means in practice

A theory result. No direct application yet.

Authors

Ebrahim Ghorbani, Matthias Mnich

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
View PDFOpen arXiv