Existem vários algoritmos de 2 aproximações para o problema de conjunto de vértices de feedback UNWEIGHTED (FVS), que estão resumidos em [4]. Observe que a redução da cobertura do vértice para o FVS preserva a aproximação. Assumindo uma conjectura de jogo única, não podemos esperar algoritmos melhores. A questão é:
Existe um gráfico não ponderado no qual parte do algoritmo realmente atinja a proporção 2?
[1] contém um exemplo tão restrito para FVS ponderada.
- Vineet Bafna e Piotr Berman e Toshihiro Fujito, http://doi.org/10.1137/S0895480196305124 ;
- Ann Becker e Dan Geiger, http://doi.org/10.1016/0004-3702(95)00004-6 ;
- Toshihiro Fujito, http://doi.org/10.1016/0020-0190(96)00094-4 ;
- Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson, http://doi.org/10.1016/S0167-6377(98)00021-2 .