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) !.
Odpowiedzi:
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 nk k , w którym to przypadku liczba potencjalnych zbiorów kliki wynosi ( nn2 co 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+logn G(n,k) k n k G(n,k) k
źródło