Zadanie pierwsze z zeszłorocznego koła z paa

Zadanie 1 (18pkt)
Udowodnij, że jeżeli P≠NP, to dla problemu minimalnego pokrycia wierzchołkowego
grafu nie istnieje:
a) wielomianowy algorytm 1-absolutnie aproksymacyjny
b) schemat FPTAS

a)  załóżmy, że istnieje algorytm, który dla dowolnego grafu myli się
o najwyżej 1 wierzchołek.

Stwórzmy teraz graf H, który będzie składał się z dwóch niepołączonych kopii grafu G.
W założeniach nie podano, że jest to problem tylko dla grafów spójnych.

Uruchamiamy nasz algorytm dla przypadków G i H.
Algorytm może się pomylić maksymalnie o 1, więc dla jednego z tych grafów problem
zostałby rozwiązany optymalnie w wielomianowym czasie. A to stoi w sprzeczności z założeniem P!=NP.

b) Załóżmy, że istnieje FPTAS dla tego problemu
maksymalnym pokryciem wierzchołkowym grafu są wszystkie jego wierzchołki.
Więc na pewno nigdy nie uzyskamy wyniku n+1 wierzchołków
(gdzie n to liczba wierzchołków w grafie naturalnie)
(a e to epsilon)
n+1 > Aopt

e = 1/(n+1)

Aopt >= Aapr >= Aopt(1+e)

Aopt >= Aapr >= Aopt + Aopt*e


Aopt >= Aapr >= Aopt + Aopt/(n+1)

n+1 jest wieksze od Aopt dlatego Aopt/(n+1) na pewno jest mniejsze niz 1.

Aopt >= Aapr >= Aopt + 1
Nie ma wierzchołków ułamkowych, wymuszamy rozwiązanie optymalne w czasie wielomianowym
a to jest sprzeczne z założeniem P!=NP