A Deterministic $(2+\epsilon )$-Approximation for Weighted Feedback Vertex Set in Tournaments

Abstract

We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\ge 2$, we give a deterministic $(2+1/k)$-approximation algorithm with running time $n^{2^{O(k)}}$, apart from polynomial dependence on the encoding length of the weights. Consequently, for every fixed $\epsilon >0$, weighted feedback vertex set in tournaments has a deterministic $(2+\epsilon )$-approximation running in time $n^{2^{O(1/\epsilon )}}$. The algorithm combines two ingredients. When the triangle graph of the tournament has bounded clique number, a chain decomposition of its transitive complement yields an exact dynamic program for a maximum-weight transitive subtournament. When the clique number is large, a structural theorem for triangle graphs supplies a constant-size strongly good cost vector. A local-ratio reduction with this cost vector gives the claimed guarantee. As a by-product, the dynamic program solves weighted feedback vertex set exactly in ${\mathcal{B}}_7$-free tournaments in time $O(n^7)$, where ${\mathcal{B}}_7$ is the family of seven-vertex tournaments with feedback vertex set number at least three.

arXiv comment8 pages, no figures