Czy problem kliki k-NP jest kompletny?

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) !.

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 $k$$k$ , w którym to przypadku liczba potencjalnych zbiorów kliki wynosi ($\frac{n}{2}$co najmniej($\binom{n}{\frac{n}{2}}$ . Stąd twój naiwny algorytm zająłby2$\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$ 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.$2^{\frac{n}{2}}$$|x|+|k|=n+\log n$$G(n,k)$$k$$n$$k$$G(n,k)$$k$