Problem zbioru niezależnego

Problem zbioru niezależnego – przykład problemu NP-zupełnego z teorii grafów.

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 największego 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.

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 ($\neg$ oznacza negację):

$(x_{1}\vee \neg x_{2}\vee \neg x_{3})\wedge (x_{1}\vee x_{2}\vee x_{4})$

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ć x₂ fałsz i x₄ prawdę. Problem stwierdzenia czy dana formuła CNF jest spełnialna jest również NP-zupełny i nazywa się CNF-SAT.

Graf skonstruowany dla przykładowej formuły powyżej

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:

1. Każdy literał z każdą jego negacją
2. 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 takim 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łę.