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 niepołą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.