Czy problem kliki k-NP jest kompletny?

23

W tym artykule w Wikipedii na temat problemu Kliki w teorii grafów stwierdza się na początku, że problem znalezienia kliki o rozmiarze K na wykresie G jest NP-zupełny:

Kliki badano również w informatyce: ustalenie, czy istnieje klika o danym rozmiarze na wykresie (problem kliki) jest NP-kompletna, ale pomimo tego wyniku twardości zbadano wiele algorytmów znajdowania klik.

Ale w tym innym artykule Wikipedii na temat problemu Kliki w CS napisano, że rozwiązanie problemu dla stałej wielkości k jest problemem w P, można go brutalnie wymusić w czasie wielomianowym.

Algorytm siły brutalnej, aby sprawdzić, czy wykres G zawiera klikę z wierzchołkiem k, i znaleźć jakąkolwiek taką klikę, która zawiera, polega na zbadaniu każdego podrozdziału z co najmniej k wierzchołkami i sprawdzeniu, czy tworzy on klikę. Ten algorytm wymaga czasu O (n ^ kk ^ 2): do sprawdzenia są podgrupy O (n ^ k), z których każdy ma krawędzie O (k ^ 2), których obecność w G musi zostać sprawdzona. Tak więc problem można rozwiązać w czasie wielomianowym, ilekroć jest stałą stałą. Jednak gdy k jest częścią danych wejściowych do problemu, czas jest wykładniczy.

Czy czegoś tu brakuje? Może różnica w brzmieniu problemu? A co oznacza ostatnie zdanie, że „Kiedy k jest częścią danych wejściowych do problemu, czas jest wykładniczy”. Dlaczego jest różnica, gdy k jest częścią danych wejściowych do problemu?

Mój pomysł polega na tym, że aby znaleźć klikę o rozmiarze k na wykresie G, najpierw wybieramy podzbiór wielkości k węzłów z G i testujemy, czy wszystkie są powiązane z innymi węzłami k, co można zrobić w sposób ciągły czas. Powtarzaj to, aż otrzymamy klikę o rozmiarze k. Liczba zestawów k węzłów, które możemy wybrać spośród G, wynosi n! / k! * (nk) !.

Raphael
źródło
13
Kompletność NP problemu zależy od tego, co uznajesz za dane wejściowe. Ponieważ problem występuje w jeśli istnieje algorytm wielomianowy do jego podjęcia. Jeśli K jest stałą (nie wejściem), algorytm jest wielomianowy w n . Jeśli k jest częścią danych wejściowych, algorytm jest wykładniczy w k . PKnkk

Odpowiedzi:

17

Właśnie rozwijając to, na co zwrócił uwagę @Lamine: gdy jest częścią wejścia, k może być tak duże jak nkk , w którym to przypadku liczba potencjalnych zbiorów kliki wynosi ( nn2co najmniej(n(nn2) . Stąd twój naiwny algorytm zająłby2n(nn2)n2 który jest wyraźnie wykładniczy w długości wejściowej| x| +| k| =n+logn. SparametryzowanawersjaG(n,k), wktórej szukamyk-klików nawykresien-vertex, przechwytuje twardość problemu w jego najbardziej uogólnionej formie, ponieważkjest częścią danych wejściowych. Stąd algorytm wieloczasowy dlaG(n,k)sugerowałby również algorytm wieloczasowy dla dowolnego określonegok.2n2|x|+|k|=n+lognG(n,k)knkG(n,k)k

Sajin Koroth
źródło