A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (That is, the algorithm looks at the lowest cost per cycle space decreased node picks it and continues to do so as long as the graph continues to have cycles.) What is the approximation guarantee of this algorithm?

Note: $\delta_H(v) = \text{cyc}(H) - \text{cyc}(H-v)$ where $ \text{cyc}(H) $ is the dimension of the cycle space of $H$.

See also Exercise 6.1 of Vazirani's "Approximation Algorithms".

Same question was posted here Minimum feedback vertex set
closed due to not defining notation reposting because notation has been clarified but problem is slow to be reopened sorry is there a process for reopening problems?
Idk if there is a stigma against posting exercises but I couldn't find an answer and I feel like the solution has a lot to do with understanding how local ratio works since local ratio yields a 2 apx and looks a lot like a greedy algorithm but the book says greedy doesn't even yield constant approx here.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.