Tight Localizations of Feedback Sets
share
The classical NP-hard feedback arc set problem (FASP) and feedback vertex set problem (FVSP) ask for a minimum set of arcs ε⊆ E or vertices ν⊆ V whose removal G∖ε, G∖ν makes a given multi-digraph G=(V,E) acyclic, respectively. The corresponding decision problems are part of the 21 NP-complete problems of R. M. Karp's famous list. 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 r ≈ 1.3606 is known to be a lower bound for the APX-hardness, at least by validation, we show that r ≤ 2. Applying the approximation preserving L-reduction from the directed FVSP to the FASP thereby allows computing feedback vertex sets with the same accuracy. Benchmarking the algorithm with state of the art alternatives yields that, for the first time, the most relevant instance class of large sparse graphs can be solved efficiently within tight error bounds. Our derived insights might provide a path to prove the APX-completeness of both problems.
READ FULL TEXT