Deterministic approximation method improves weighted feedback vertex sets
A Deterministic $(2+\varepsilon)$-Approximation for Weighted Feedback Vertex Set in Tournaments
Data Structures and Algorithms
Summary
The weighted feedback vertex set problem in tournaments asks how to remove the smallest total weight of vertices to eliminate all cycles. The authors developed a new algorithm that finds a solution close to the best possible, with a guarantee within about twice the minimal weight plus a small margin. Their approach combines exact calculations when certain graph structures are simple, and an approximation technique when those structures are complex. This method runs efficiently for any fixed margin of error and applies exactly to some special cases of tournaments.
What this means in practice
- •For network schedulers: Optimize feedback elimination in scheduling conflicts modeled by tournament graphs using a near-optimal deterministic algorithm.
- •For bioinformatics tool developers: Implement efficient cycle-breaking tools for weighted tournament data to improve analysis of directional biological interactions.
A theory result. No direct application yet.
Authors
Hanqing Li, Zihan Wu
Abstract
We study the weighted feedback vertex set problem in tournaments. For every fixed integer $k\geq 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 $\varepsilon>0$, weighted feedback vertex set in tournaments has a deterministic $(2+\varepsilon)$-approximation running in time $n^{2^{O(1/\varepsilon)}}$. 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.