Algorytm

Klika problem jest znany -Complete problemem przy czym wielkość wymaganej klika jest częścią wejścia. Jednak problem kliki k ma trywialny wielomianowy algorytm czasu ( O ( n k ), gdy k jest stałe). Interesują mnie najlepiej znane górne granice, gdy k jest stałe.$NP$$O(n^k)$$k$

Czy istnieje algorytm z czasem wykonania ? O ( N K ) -czas algorytm jest także do przyjęcia. Ponadto, czy istnieje jakaś teoretyczna konsekwencja dla istnienia takich algorytmów?$O(n^{k-1})$$o(n^k)$

3-klikę można znaleźć na wykresie konwersji G w czasie O ( n ω ) , gdzie ω < 2,376 jest wykładnikiem mnożenia macierzy, a w przestrzeni O ( n 2 ) przez Itai i Rodeh [1] . Zasadniczo pokazują, że G zawiera trójkąt wtedy i tylko wtedy, gdy ( A ( G ) ) 3 ma niezerowy wpis na swojej głównej przekątnej. Ponieważ trójkąt jest również cyklem C $n$$G$$O(n^\omega)$$\omega < 2.376$$O(n^2)$$G$$(A(G))^3$$C_3$, można zastosować ogólne metody wyszukiwania cykli do wykrywania trójkątów. Alon, Yuster i Zwick pokazują, w jaki sposób można wykryć trójkąty na wykresie krawędzi w czasie O ( m 2 ω / ( ω + 1 ) ) = O ( m 1,41 ) [6].$m$$O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$

Przez długi czas najbardziej znane były wyniki Nesetril i Poljak [2]; pokazali, że liczbę klików o wielkości można znaleźć w przestrzeni O ( n ω k ) i O ( n 2 k ) . Wreszcie, Eisenbrand i Grandoni [3] poprawili wynik Nesetril i Poljak dla kliki ( 3 k + 1 ) i kliki ( 3 k + 2 ) dla małych wartości k . W szczególności podali algorytmy znajdowania klików o rozmiarach 4, 5 i 7 w czasie $3k$$O(n^{\omega k})$$O(n^{2k})$$(3k+1)$$(3k+2)$$k$ , O ( n 4.220 ) i O ( n 5.714 ) , odpowiednio.$O(n^{3.334})$$O(n^{4.220})$$O(n^{5.714})$

O ile mi wiadomo, dla ogólnego problem projektowania lepszych algorytmów jest otwarty. Dla możliwych konsekwencji lub rozważań teoretycznych dotyczących złożoności Downey i Fellows (patrz np. [4]) wykazali, że k- klika z parametrem k jest W [ 1 ] - twarda. Klasa W [ 1 ] oznacza klasę sparametryzowanych problemów decyzyjnych redukowalnych do CLIQUE ze sparametryzowanymi redukcjami. Uważa się, że CLIQUE nie jest możliwy do ustalenia z ustalonymi parametrami. Istnieją setki innych problemów, o których wiadomo, że są równoważne z CLIQUE przy sparametryzowanych redukcjach. Ponadto Feige i Kilian [5, sekcja 2] mają wynik, mówiąc, że gdy $k$$k$$k$$W[1]$$W[1]$$k$jest częścią wejścia i , to algorytm polytime nie może istnieć.$k \approx \log n$

Jeśli weźmiesz pod uwagę pewne ograniczone klasy grafów, możesz rozwiązać problem w czasie liniowym na grafach akordowych. Wystarczy obliczyć drzewo kliki wykresu cięciwy w czasie O ( n + m ) , a następnie sprawdzić, czy jakaś klika ma rozmiar dokładnie k . Na wykresach płaskich można również znaleźć trójkąty w czasie O ( n ), stosując metody [6].$G$$O(n+m)$$k$$O(n)$

[1] Itai, Alon i Michael Rodeh. „Znalezienie minimalnego obwodu na wykresie”. SIAM Journal on Computing 7.4 (1978): 413–423.

[2] Nešetřil, Jaroslav i Svatopluk Poljak. „O złożoności problemu podgrupy”. Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415–419.

[3] Eisenbrand, Friedrich i Fabrizio Grandoni. „O złożoności kliki o stałym parametrze i dominującego zestawu.” Theoretical Computer Science 326.1 (2004): 57-67.

[4] Downey, RG i Michael R. Fellows. „Podstawy sparametryzowanej złożoności”. Undegraduate Texts in Computer Science, Springer-Verlag (2012).

[5] Feige, Uriel i Kilian, Joe. „O ograniczonym kontra wielomianowym niedeterminizmie”. Chicago Journal of Theoretical Computer Science. (1997)

[6] Alon, Noga, Raphael Yuster i Uri Zwick. „Znajdowanie i liczenie podanych cykli długości”. Al Algorytmica 17.3 (1997): 209–223.