2
$\begingroup$

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

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Please define your notations. $\endgroup$
    – azam
    Jan 13 '16 at 12:21
  • 1
    $\begingroup$ What do you think? We expect you to make a serious effort before asking a question. We will not solve your exercise for you. $\endgroup$
    – Yuval Filmus
    Jan 13 '16 at 18:29
  • $\begingroup$ @YuvalFilmus is csstackexchange not allow posting exercises? I can't seem to find solutions to these exercises. $\endgroup$
    – Hao S
    Aug 20 '19 at 2:26
  • $\begingroup$ @HaoS posting exercises is ok, but we expect you to show significant effort. This question looks more like a problem dump which tend to get closed. $\endgroup$
    – Juho
    Aug 20 '19 at 8:09
  • $\begingroup$ @YuvalFilmus I don't quite understand what you mean by problem dump I'm kinda curious as to a counterexample since the 2 approximation looks kind of like a greedy approach so is it just the lack of a reverse deletion step? or is there more to the layering technique? $\endgroup$
    – Hao S
    Aug 20 '19 at 16:18