Posadzone klika - Planted clique

W teorii złożoności obliczeniowej , A obsadzone klika lub ukryty klika w nieukierunkowane wykresu jest klika utworzone z innego wykresu poprzez wybranie podzbioru wierzchołków i dodanie krawędzie pomiędzy każdą parę wierzchołków w podgrupie. Sadzone problem kliki jest algorytmiczne problem odróżniania losowych wykresy z wykresów, które mają posadzone kliki. Jest to odmiana problem kliki ; może być rozwiązany w quasi wielomianem czasu , ale przypuszcza się, aby nie być rozpuszczalny w czasie wielomianowym dla wartości pośrednich klika wielkości. Hipoteza, że nie istnieje wielomian rozwiązanie czas nazywany jest obsadzone klika przypuszczenie ; jest ono stosowane jako obliczeniowa twardości założeniu .

Definicja

Klika na wykresie jest podzbiorem wierzchołki, z których wszystkie są przylegające do siebie. Obsadzone klika jest klika utworzony z innego wykresu dodając krawędzie pomiędzy wszystkimi parami wybranego podzbioru wierzchołków.

Obsadzonej problem kliki może być sformalizowane jako problemu decyzyjnego nad losowej dystrybucji na wykresach parametryzowane dwóch liczb, n (liczba wierzchołków) oraz K (rozmiar kliki). Parametry te mogą być wykorzystywane do generowania wykresu w następującym procesie losowego:

1. Tworzyć losowe wykres Erdősa-Renyi na n wierzchołków wybierając niezależnie dla każdej pary wierzchołków czy to krawędź łączącą tę parę, z prawdopodobieństwem 1/2 dla każdej pary.
2. Zadecydować, czy należy dodać klika na wykresie z prawdopodobieństwem 1/2; Jeżeli nie, należy zwrócić wykres utworzonego w etapie 1.
3. Losowo wybrać podzbiór k z n wierzchołków i dodać krawędzi (jeśli nie jest już obecny) pomiędzy każdą parą wybranych wierzchołków.

Problem polega zatem na celu określenie, czy jeden z algorytmem z wykresów wynikające z tego procesu zawiera klika przynajmniej k wierzchołków.

Z dużym prawdopodobieństwem, rozmiar największej klika AA, n -Vertex losowej wykresie znajduje się w pobliżu 2 log ₂ n . A gdy k jest większe od pierwiastka kwadratowego n , wierzchołki obsadzone kliki mogą być uznane za posiadające niezwykle duże stopni , dzięki czemu zasadzone klika łatwe do znalezienia. Dlatego też, najbardziej interesujący zakres wartości parametru k jest pomiędzy tymi dwoma wartościami,

${\ Displaystyle 2 \ _ log {2} n \ ll K \ ll {\ sqrt {n}}.}$

algorytmy

duże kliki

Dla dostatecznie dużej wartości parametru k , obsadzonej klika problem może być rozwiązany (z dużym prawdopodobieństwem) w czasie wielomianowym.

Kučera (1995) zauważa, że gdy wtedy prawie na pewno wszystkie wierzchołki zasadzone kliki mają wyższy stopień niż wszystkie wierzchołki spoza kliki, co klika bardzo łatwe do znalezienia. Opisuje on modyfikację procesu losowego generowania posadzone instancje kliki, która sprawia, że stopnie wierzchołków bardziej jednolite nawet dla dużych wartości  k , ale pokazuje, że mimo tej modyfikacji obsadzonej klika nadal może znaleźć szybko.${\ Displaystyle k = \ Omega ({\ sqrt {n \}} log n)}$

Alon, Krivelevich & Sudakov (1998) dowodzą dla obsadzone kliki znaleźć można z dużym prawdopodobieństwem za pomocą następującej metody: ${\ Displaystyle k> 10 {\ sqrt {n}}}$

1. Obliczyć wektor własny z matrycy przylegania odpowiadającej jej drugiej największej wartości własnej .
2. Wybierz k wierzchołków, których współrzędne w ten wektor własny mają największe wartości bezwzględne .
3. Zwraca zbiór wierzchołków, które sąsiadują z co najmniej 3/4 wybranych wierzchołków.

Pokazują one, jak zmodyfikować tę technikę tak, że nadal działa, gdy k jest przynajmniej proporcjonalny do jakiejś wielokrotności pierwiastka kwadratowego z liczby wierzchołków. Duże posadzone kliki można również znaleźć za pomocą programowania półokreśloną . Kombinatorycznej technika oparta na losowo wierzchołki próbkowania może osiągnąć to samo ograniczenie na k i działa w czasie liniowym .

Quasipolynomial czas

Jest również możliwe, aby rozwiązać problem kliki posadzone, niezależnie od wyboru k , w quasi-wielomian czasu . Ponieważ największe klika w losowej wykresie zwykle ma rozmiar w 2 log ₂ n , obsadzone klika rozmiarze K (jeśli istnieje) znajduje się z dużym prawdopodobieństwem, następującym sposobem:

1. Pętli wszystkich zestawów S z wierzchołków.${\ Displaystyle \ min (k, 3 \ _ log {2} n)}$
2. Dla każdego wyboru S , test, czy S jest klika. Jeżeli tak jest, i powrócić S . W przeciwnym razie, znaleźć zestaw T wierzchołków, które przylega do wszystkich wierzchołków S . Jeśli powrócić T .${\ Displaystyle | S | = k}$${\ Displaystyle | T | \ geq k}$

Czas pracy tego algorytmu jest quasipolynomial, ponieważ istnieje wiele możliwości wyboru quasipolynomially S do pętli nad. Ten sposób gwarantuje się, aby spróbować zestaw S , który jest podzbiorem obsadzone klika; z dużym prawdopodobieństwem, zestaw T będzie się składać tylko z innymi członkami zasadzone kliki.

W założeniu twardości

Obsadzonej klika przypuszczenie jest przypuszczenie, że nie ma czasu, że wielomian algorytm bierze postaci wykresów wejściowych produkowanych przez zasadzone procesu kliki i wyróżnia te z posadzonych klik od tych, które nie mają posadzone klik z prawdopodobieństwem znacznie lepsze niż przypadek.

Hazan & Krauthgamer (2011) stosowany przy założeniu, że znalezienie posadzone klik jest twarde jak obliczeniowa twardość założenie , aby udowodnić, że jeśli tak, to również trudne do zbliżenia najlepszą równowagę Nasha w grze dla dwóch graczy. Obsadzonej klika hipoteza została również zastosowana jako założeniu twardości pokazać trudności testowania nieruchomość k -independence losowych rozkładów, znalezienie klastrów w sieci społecznej oraz uczenia maszynowego .

Referencje