# Tight Localizations of Feedback Sets

arXiv: https://arxiv.org/abs/2001.01440 · HTML: https://mlsanity.com/paper/2001.01440/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jan 2020.

## Built on by (most cited first, 1 of 1)

- [Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons](https://mlsanity.com/paper/2412.16181/) (2024)

## Abstract (arXiv)

The classical NP-hard feedback arc set problem (FASP) and feedback vertex set problem (FVSP) ask for a minimum set of arcs varepsilon subseteq E or vertices nu subseteq V whose removal Gsetminus varepsilon, Gsetminus nu makes a given multi-digraph G=(V,E) acyclic, respectively. Though both problems are known to be APX-hard, approximation algorithms or proofs of inapproximability are unknown. We propose a new O(|V||E|4)-heuristic for the directed FASP. While a ratio of r ≈ 1.3606 is known to be a lower bound for the APX-hardness, at least by empirical validation we achieve an approximation of r ≤ 2. The most relevant applications, such as circuit testing, ask for solving the FASP on large sparse graphs, which can be done efficiently within tight error bounds due to our approach.