  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 $G\setminus \varepsilon$, $G\setminus
\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
$\mathcal{O}(|V||E|^4)$-heuristic for the directed FASP. While a ratio of $r
\approx 1.3606$ is known to be a lower bound for the APX-hardness, at least by
empirical validation we achieve an approximation of $r \leq 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.
