Tight Localizations of Feedback Sets
Michael Hechta, Krzysztof Gonciarza, Szabolcs Horvátb
- aMax Planck Institute of Molecular Cell Biology and Genetics, Center for Systems Biology Dresden, Germany
- bMax Planck Institute of Molecular Cell Biology and Genetics, Center for Systems Biology Dresden and Max Planck Institute for the Physics of Complex Systems, Dresden, Germany
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
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. Though both problems are known to be APX–hard, constant ratio approximations or proofs of inapproximability are unknown. We propose a new universal 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. Most of the relevant applications, such as circuit testing , ask for solving the FASP on large sparse graphs, which can be done efficiently within tight error bounds with our approach.
TL;DRThis work proposes a new universal O(|V||E|4)–heuristic for the directed FASP and achieves an approximation of r ≤ 2.6 within tight error bounds with this approach. (Semantic Scholar)