Problem zbioru niezależnego
Z Wikipedii
W teorii złożoności obliczeniowej problem zbioru niezależnego jest przykładem problemu NP-zupełnego z teorii grafów.
[edytuj] Opis
Dla danego grafu G, zbiór niezależny to zbiór wierzchołków nie połączonych żadnymi krawędziami. Innymi słowy, podgraf indukowany przez ten zbiór nie ma żadnych krawędzi, a jedynie izolowane wierzchołki. Problem zbioru niezależnego to pytanie czy dla danego grafu G i liczby k, istnieje w G zbiór niezależny o k wierzchołkach. Odpowiadający mu problem optymalizacyjny to problem maksymalnego zbioru niezależnego, polegający na znalezieniu zbioru niezależnego o największej liczbie wierzchołków. Mając rozwiązanie dla problemu decyzyjnego, można za pomocą wyszukiwania binarnego rozwiązać również problem optymalizacyjny, używając O(log |V|) razy tamtego rozwiązania. Problem ten nie posiada aproksymacji z czynnikiem stałym jeśli P≠NP.
[edytuj] Dowód NP-zupełności
Łatwo stwierdzić że problem ten należy do klasy NP, ponieważ mając podany zbiór wierzchołków możemy w czasie liniowym sprawdzić czy nie ma pomiędzy nimi żadnej krawędzi. Aby pokazać że jest to problem NP-trudny, możemy pokazać redukcję problemu spełnialności formuł logicznych (SAT) do niego.
Pierwszym krokiem jest przekształcenie formuły do postaci koniunkcyjnej (CNF). W tej postaci:
- formuła jest koniunkcją (i) klauzul
- każda klauzula jest alternatywą (lub) literałów
- każdy literał jest zmienną lub jej negacją.
Przykładowo, poniższa formuła jest w postaci CNF (
oznacza negację):
Taka formuła jest spełnialna jeśli możemy przyporządkować zmiennym wartości prawda/fałsz tak żeby w każdej klauzuli przynajmniej jeden literał był prawdziwy. Przykładowo dla powyższej formuły możemy przyporządkować x2 fałsz i x4 prawdę. Problem stwierdzenia czy dana formuła CNF jest spełnialna jest również NP-zupełny i nazywa się CNF-SAT.
Opiszemy teraz algorytm wielomianowy przekształcający problem CNF-SAT w problem zbioru niezależnego. Na początku tworzymy wierzchołek dla każdego literału w formule, łącznie z jego powtórzeniami. Następnie łączymy krawędziami:
- Każdy literał z każdą jego negacją
- Każde dwa literały które należą do tej samej klauzuli
Twierdzimy że powstały graf zawiera niezależny zbiór rozmiaru k wtedy i tylko wtedy gdy formuła od której zaczęliśmy była spełnialna.
Załóżmy że znaleźliśmy wartościowanie które spełnia formułę. Możemy wtedy wybrać z każdej formuły po jednym literale który jest prawdziwy w takich wartościowaniu. Ten zbiór jest niezależny ponieważ zawiera tylko po jednym literale z każdej klauzuli (nie ma krawędzi typu 2), i wartościowanie nie dopuszcza żeby literał i jego negacja były jednocześnie prawdziwe (nie ma krawędzi typu 1).
Z drugiej strony, załóżmy że znaleźliśmy zbiór niezależny rozmiaru k. Nie może on zawierać dwóch literałów w jednej klauzuli, ponieważ byłyby one połączone krawędzią. Zatem musi zawierać po jednym literale w każdej z k klauzul. Nie może zawierać też żadnego literału jednocześnie z jego negacją, ponieważ byłyby one też połączone krawędzią. Oznacza to że jeśli wybierzemy wartościowanie które nada tym k literałom wartość prawda, to będzie ono spełniało początkową formułę.
