# Minimum feedback vertex set [closed]

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$$.