A Pseudo ∈-Approximate Algorithm For Feedback Vertex Set

While the picture of approximation complexity class becomes clear for most combinatorial optimization problems, it remains an open question whether Feedback Vertex Set can be approximated within a constant ratio in directed graph case. In this paper we present an approximation algorithm with performance bound L _max −1, where L _max is the largest length of essential cycles in the graph G(V,E). The worst case bound is $$\left\lfloor {\sqrt {{{\left| V \right|}^2} - \left| V \right| - \left| E \right| + 1} } \right\rfloor $$ which, in general, is inferior to Seymour’s recent result [14], but becomes a small constant for some graphs. Furthermore, we prove the so-called pseudo ∈-approximate property, i.e. FVS can be divided into a class of disjoint NP -complete subproblems, and our heuristic becomes ∈-approximate for each one of these subproblems.