Feedback Vertex Set - Approximation

Approximation

The problem is APX-complete, which directly follows from the APX-completeness of the vertex cover problem, and the existence of an approximation preserving L-reduction from the vertex cover problem to it. The best known approximation algorithm on undirected graphs is by a factor of two, based on the Becker-Geiger theorem.

Read more about this topic:  Feedback Vertex Set