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

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by Yuval Filmus, D.W.♦ Jan 13 '16 at 19:33

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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 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 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 at 16:18