Ejemplos ajustados para aproximar el problema del conjunto de vértices de retroalimentación

Existen varios algoritmos de aproximación de 2 para el problema de conjunto de vértices de retroalimentación SIN PESAR (FVS), que se resumen en [4]. Tenga en cuenta que la reducción de la cubierta de vértices a FVS es la preservación de aproximación. Suponiendo una conjetura de juego única, no podemos esperar mejores algoritmos. La pregunta es:

¿Hay un gráfico no ponderado en el que parte del algoritmo realmente alcanza la relación 2?

[1] contiene una instancia tan ajustada para FVS ponderado.

1. Vineet Bafna y Piotr Berman y Toshihiro Fujito, http://doi.org/10.1137/S0895480196305124 ;
2. Ann Becker y 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 .

Creo que puedes hacer el algoritmo clásico de relación local de Bafna et al. dé una aproximación en la siguiente familia de gráficos:$2-o(1)$

Tome como K n , n (el gráfico completo de bipertita con n vértices en cada lado), y luego elimine un solo borde. A continuación se muestra que el algoritmo puede generar todos los vértices "azules" ( 2 n - 4 en número) como la aproximación FVS, mientras que hay un FVS mucho más pequeño para G n .$G_n$$K_{n,n}$$n$$2n-4$$G_n$

(observe que no hay borde entre los vértices verde azulado).

El FVS óptimo contiene vértices (tome todos los vértices a la derecha, excepto el superior).$n-1$

Ahora no hay ciclos semi-disjuntos, y los grados de vértices son los siguientes:

1. $n$
2. $n-1$

$F$

$F$

$F$$FVS$$2n-4$

$\frac{2n-4}{n-1}=2-o(1)$