Megoldás: 2.7
Mutatunk egy példát, amikor a módosított algoritmus is ,,nagyon rossz" eredményt ad. A
G gráfot a következőképpen definiáljuk. Legyen
H egy
m elemű ponthalmaz, ennek pontjai között ne fusson él. A gráf ezen kívül még egy
x pontból és egy
m+1 elemű
J ponthalmazból áll.
x és
J minden pontja össze van kötve
H minden pontjával, továbbá
J teljes gráfot feszít.
Ebben a gráfban
x a legkisebb fokú pont, tehát algoritmusunk először ezt a pontot választja ki
V-be és elhagyja összes szomszédját, vagyis
H pontjait - tehát épp a maximális független ponthalmazt! Megmaradnak
J pontjai, amelyek viszont egy teljes gráfot alkotnak, tehát közülük már csak egyetlen pontot választhat ki az algoritmus.
Így összesen két független pontot talál, holott a maximális független ponthalmaz
m elemű. Tehát a maximálisnak csak
m/2-ed részét találja meg. Mivel
m/2 akármilyen nagy lehet, ez az algoritmus nem szuboptimális.