Problem zbioru niezależnego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Opis[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Ł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.

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łę.