Contoh ketat untuk memperkirakan masalah set vertex umpan balik

Ada beberapa algoritme 2-aproksimasi untuk masalah set vertex umpan balik (FVS) TAK TERBATAS, yang dirangkum dalam [4]. Perhatikan bahwa pengurangan dari penutup simpul ke FVS adalah perkiraan-melestarikan. Dengan asumsi dugaan Game Unik, kami tidak dapat mengharapkan algoritma yang lebih baik. Pertanyaannya adalah:

Apakah ada grafik tidak tertimbang di mana beberapa algoritma benar-benar mencapai rasio 2?

[1] berisi contoh ketat untuk FVS tertimbang.

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

$2-o(1)$

$G_n$$K_{n,n}$$n$$2n-4$$G_n$

(perhatikan tidak ada tepi antara simpul teal).

$n-1$

Sekarang tidak ada siklus semi-disjoint, dan derajat simpul adalah sebagai berikut:

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

$F$

$F$

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

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