Tight examples for approximating the feedback vertex set problem

Question

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.

Answer 1

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.