The specific algorithm I am referring to is Algorithm 6.8 from Vazirani's book "Approximation Algorithms". The book is legally available online here, and the algorithm is on page 58 (76 in the pdf).

The algorithm is pretty simple (especially if you're familiar with the layering technique), but in any case I'm only interested in tight examples, which usually implies "degenerated" (trivial) runs of the algorithm.

I understand the tight example the book has provided (Example 6.10, found one page after the algorithm), but I'm looking for one that uses a simple graph (i.e. without parallel edges).

For an example without parallel edges, the author suggests "a vertex with very high weight" to "be placed on every edge". I have two (independent, related and simple) questions regarding this:

  1. Does Example 6.10 work "as is" (with the only change being that you don't duplicate every edge)? I think that if you simply remove a perfect matching from $K_{n,n}$, then the algorithm might output a FVS with $2n-5$ vertices, where the 5 not-chosen vertices can be any 3 vertices from one side and any 2 vertices from the other side. This is indeed a $2-o(1)$ approximation, as desired.

  2. What is the meaning of the sentence "a vertex with very high weight can be placed on every edge"? I can interpret this in two ways:

    • One is that we'll have vertices with weight $\infty$ on one side, and vertices with cyclomatic weight on the other. This is not a good example because the algorithm can output a set of $n$ vertices (which is optimal).
    • A second interpration is that "in the middle" of each edge we add a new vertex (i.e. if we had an edge $(u,v)$, now we'll have $(u,a)$ and $(a,v)$ for some new vertex $a$ with weight $\infty$). This example indeed leads to a solution which is a $2-o(1)$ approximation, but I'm not sure why is it worth the trouble of using vertices "with very high weight" when a much simpler example exists (in case the answer to my first question is yes).

    How would you interpret this sentence?

  • $\begingroup$ Please restrict yourself to one question per post. You ask several. $\endgroup$ – Raphael Sep 7 '15 at 10:48

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.