Tight examples for approximating the feedback vertex set problem

There are several 2-approximation algorithms for the UNWEIGHTED feedback vertex set problem (FVS), which are summarized in [4]. Note that the reduction from vertex cover to FVS is approximation-preserving. Assuming Unique Game Conjecture, we cannot expect better algorithms. The question is:

Is there an unweighted graph on which some of the algorithm really reaches ratio 2?

[1] contains such a tight instance for weighted FVS.

1. Vineet Bafna and Piotr Berman and Toshihiro Fujito, http://doi.org/10.1137/S0895480196305124;
2. Ann Becker and Dan Geiger, http://doi.org/10.1016/0004-3702(95)00004-6;
3. Toshihiro Fujito, http://doi.org/10.1016/0020-0190(96)00094-4;
4. Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson, http://doi.org/10.1016/S0167-6377(98)00021-2.

I think you can make the classical local ratio algorithm by Bafna et al. give a $2-o(1)$ approximation on the following family of graphs:

Take $G_n$ to be a $K_{n,n}$ (the complete bipertite graph with $n$ vertices on each side), and then delete a single edge. The following shows that the algorithm might output all of the "blue" vertices ($2n-4$ in number) as the FVS approximation, while there's a much smaller FVS for $G_n$.

(notice there's no edge between the teal vertices).

The optimal FVS is contains $n-1$ vertices (take all of the vertices on the right, except the top one).

Now there are no semi-disjoint cycles, and the vertices degrees are as follows:

1. Blue / Purple vertices - degree $n$.
2. Teal vertices - degree $n-1$.

This means that the all of the blue/purple vertices will be inserted first into the stack at arbitrary order (the teal vertices enters the stack at the end and are the first to be deleted from $F$).

Assuming that the purple vertices will pushed after (and popped before) the blue ones, they will be removed from $F$ which will be updated to contain all of the blue vertices.

From this point on, no other vertex can be deleted from $F$ (otherwise there will be a cycle using the teal/purpule vertices), and the resulting $FVS$ has size $2n-4$.

This gives us a $\frac{2n-4}{n-1}=2-o(1)$ approximation ratio, hence showing the analysis is tight even for the unweighted case.

• Thank you! This is exactly what I want. Just a small comment: if I understand Bafna et al.'s algorithm correctly, the purple vertices will not be inserted into the stack, as after all blue vertices are in, the remaining graph is acyclic (a path on four vertices). Apr 6 '14 at 17:20
• @YixinCao - while the graph is indeed acyclic after the blue ones have been removed, they still loop over all vertices of residual weight 0, and the blue and purple ones get to 0 on the same iteration. At least that's what it looks like from their paper.
– R B
Apr 6 '14 at 17:24
• They conduct cleanup after each step as follows (copied from the paper): While $G$ contains a vertex of degree at most $1$, remove it along with any incident edges. Apr 6 '14 at 17:34
• sorry, you're correct, and I misunderstood something. Apr 6 '14 at 17:37