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: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.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?
Tight examples: Feedback vertex set 2-approximation algorithm
algorithms;graphs;approximation