Problem kliki - Clique problem

Algorytm brute force znajdzie 4-klika na wykresie 7 wierzchołka (dopełnienie 7 wierzchołków grafu ścieżki ) systematycznie sprawdzając C (7,4) = 35 subgraphs 4 wierzchołków dla kompletności.

W informatyce The problem kliki jest obliczeniowa problem znalezienia klik (podzbiory wierzchołków, wszystkie przylegające do siebie, zwanych również kompletnych subgraphs ) w wykresie . Ma kilka różnych sformułowań w zależności od tego, które kliki i jakie informacje o klikach należy znaleźć. Typowe sformułowania problemu kliki obejmują znalezienie maksymalnej kliki (kliki o największej możliwej liczbie wierzchołków), znalezienie kliki o maksymalnej wadze w grafie ważonym, wymienienie wszystkich maksymalnych klik (klik, których nie można powiększyć) oraz rozwiązanie problemu decyzyjnego sprawdzania, czy wykres zawiera klikę większą niż dany rozmiar.

Problem kliki pojawia się w następującym rzeczywistym świecie. Rozważmy sieć społecznościową , gdzie wierzchołki wykresu reprezentują ludzi, a krawędzie grafu reprezentują wzajemną znajomość. Wtedy klika reprezentuje podzbiór ludzi, którzy wszyscy się znają, a algorytmy wyszukiwania klik można wykorzystać do odkrycia tych grup wspólnych przyjaciół. Oprócz zastosowań w sieciach społecznościowych, problem kliki ma również wiele zastosowań w bioinformatyce i chemii obliczeniowej .

Większość wersji problemu kliki jest trudna. Problem decyzyjny kliki jest NP-zupełny (jeden z 21 NP-zupełnych problemów Karpa ). Problem ze znalezieniem maksymalnej kliki jest zarówno trudny do rozwiązania, jak i trudny do przybliżenia . A wypisanie wszystkich maksymalnych klik może wymagać czasu wykładniczego, ponieważ istnieją grafy z wykładniczo wieloma maksymalnymi klikami. Dlatego znaczna część teorii problemu kliki jest poświęcona identyfikacji specjalnych typów grafów, które dopuszczają bardziej wydajne algorytmy, lub ustalaniu trudności obliczeniowej ogólnego problemu w różnych modelach obliczeń.

Aby znaleźć maksymalną klikę, można systematycznie sprawdzać wszystkie podzbiory, ale tego rodzaju przeszukiwanie siłowe jest zbyt czasochłonne, aby było praktyczne w przypadku sieci składających się z więcej niż kilkudziesięciu wierzchołków. Chociaż nie jest znany żaden algorytm wielomianowy dla tego problemu, znane są bardziej wydajne algorytmy niż przeszukiwanie siłowe. Na przykład algorytm Brona-Kerboscha może być użyty do wymienienia wszystkich maksymalnych klik w najgorszym przypadku optymalnym czasie, a także możliwe jest wymienienie ich w czasie wielomianowym na klikę.

Historia i aplikacje

Badanie pełnych podgrafów w matematyce poprzedza terminologię „kliki”. Na przykład pełne podgrafy pojawiły się wcześnie w literaturze matematycznej w teoretycznym grafie przeformułowaniu teorii Ramseya przez Erdősa i Szekeresa (1935) . Ale termin „klik” i problem algorytmicznej listy klik pochodzą z nauk społecznych, gdzie pełne podgrafy są używane do modelowania społecznych klik , grup ludzi, którzy wszyscy się znają. Luce i Perry (1949) wykorzystali grafy do modelowania sieci społecznych i dostosowali terminologię nauk społecznych do teorii grafów. Jako pierwsi nazwali kompletne podgrafy „klikami”. Pierwszym algorytmem rozwiązania problemu kliki jest algorytm Harary'ego i Rossa (1957) , których motywowało zastosowanie socjologiczne. Badacze nauk społecznych zdefiniowali również różne inne typy klik i maksymalne kliki w sieci społecznej, „spójne podgrupy” ludzi lub aktorów w sieci, z których każdy łączy jeden z kilku różnych rodzajów relacji łączności. Wiele z tych uogólnionych pojęć kliki można również znaleźć, konstruując graf nieskierowany, którego krawędzie reprezentują powiązane pary aktorów z sieci społecznościowej, a następnie stosując algorytm dla problemu kliki do tego grafu.

Od czasu pracy Harary'ego i Rossa wielu innych opracowało algorytmy dla różnych wersji problemu kliki. W latach 70. naukowcy zaczęli badać te algorytmy z punktu widzenia analizy najgorszego przypadku . Zobacz na przykład Tarjan i Trojanowski (1977) , wczesną pracę o najgorszym przypadku złożoności problemu maksymalnej kliki. Również w latach 70., poczynając od prac Cooka (1971) i Karpa (1972) , badacze zaczęli wykorzystywać teorię NP-zupełności i związanych z nią wyników nierozwiązywalności, aby zapewnić matematyczne wyjaśnienie postrzeganej trudności problemu kliki. W latach 90. przełomowa seria artykułów rozpoczynająca się od Feige et al. (1991) i donosił w The New York Times , wykazał, że (przy założeniu P NP ) nie jest nawet możliwe dokładne i efektywne przybliżenie problemu.

Algorytmy znajdowania klik zostały wykorzystane w chemii , aby znaleźć związki chemiczne pasujące do struktury docelowej oraz modelować dokowanie molekularne i miejsca wiązania reakcji chemicznych. Można je również wykorzystać do znalezienia podobnych struktur w różnych cząsteczkach. W tych zastosowaniach tworzy się wykres, w którym każdy wierzchołek reprezentuje dopasowaną parę atomów, po jednym z każdej z dwóch cząsteczek. Dwa wierzchołki są połączone krawędzią, jeśli dopasowania, które reprezentują, są ze sobą kompatybilne. Zgodność może oznaczać, na przykład, że odległości między atomami w dwóch cząsteczkach są w przybliżeniu równe, z pewną określoną tolerancją. Klika na tym wykresie reprezentuje zestaw dopasowanych par atomów, w których wszystkie dopasowania są ze sobą kompatybilne. Szczególnym przypadkiem tej metody jest wykorzystanie iloczynu modularnego grafów do zredukowania problemu znalezienia maksymalnego wspólnego podgrafu indukowanego dwóch grafów do problemu znalezienia maksymalnej kliki w ich iloczynie.

W automatycznym generowaniu wzorców testowych znajdowanie klik może pomóc w ograniczeniu rozmiaru zestawu testowego. W bioinformatyce algorytmy znajdowania klik zostały wykorzystane do wywnioskowania drzew ewolucyjnych , przewidywania struktur białkowych i znajdowania ściśle oddziałujących na siebie klastrów białek. Umieszczenie klik na wykresie zależności jest ważnym krokiem w analizie pewnych procesów losowych. W matematyce przypuszczenie Kellera na kafli twarzą w twarz hipersześcianach została obalona przez Lagarias & Shor (1992) , który używany jest algorytm kliki rozpoznawczej na towarzyszącym wykresie znaleźć kontrprzykład.

Definicje

Przedstawiony wykres ma jedną maksymalną klikę, trójkąt {1,2,5} i cztery kolejne maksymalne kliki, pary {2,3}, {3,4}, {4,5} i {4,6} .

Nieukierunkowane wykres jest utworzony przez skończonego zbioru z wierzchołków i zestaw nieuporządkowanych par wierzchołki, które zwane są krawędzie . Umownie, w analizie algorytmów liczba wierzchołków grafu jest oznaczona przez $n,$ a liczba krawędzi przez $m$ . Klika na wykresie $G$ jest pełna subgraph z $G$ . Oznacza to, że jest to podzbiór $K$ wierzchołków taki, że każde dwa wierzchołki w $K$ są dwoma punktami końcowymi krawędzi w $G$ . Ilość klika jest klika na których nie więcej wierzchołki mogą być dodawane. Dla każdego wierzchołka $v,$ który nie jest częścią maksymalnej kliki, musi istnieć inny wierzchołek $w,$ który znajduje się w klikie i nie sąsiaduje z $v$ , zapobiegając dodaniu $v$ do kliki. Maksymalna klika jest klika, która obejmuje największą liczbę wierzchołków. Liczba kliki $ω (G)$ jest liczbą wierzchołków w maksymalnej klikie $G$ .

Zbadano kilka ściśle powiązanych problemów ze znajdowaniem klik.

W zagadnieniu maksymalnej kliki, dane wejściowe są grafem nieskierowanym, a wynikiem jest maksymalna klika w grafie. Jeśli istnieje kilka maksymalnych klik, jedna z nich może być wybrana arbitralnie.
W problemie ważonej maksymalnej kliki, dane wejściowe to nieskierowany graf z wagami na jego wierzchołkach (lub rzadziej krawędziach), a wynikiem jest klika o maksymalnej całkowitej wadze. Problem maksymalnej kliki to szczególny przypadek, w którym wszystkie wagi są równe. Oprócz problemu optymalizacji sumy wag, zbadano również inne, bardziej skomplikowane problemy optymalizacji bikryterialnej.
W zadaniu z listą maksymalnych klik dane wejściowe to graf nieskierowany, a wynikiem jest lista wszystkich jego maksymalnych klik. Problem maksymalnej kliki może być rozwiązany przy użyciu jako podprogramu algorytmu dla problemu maksymalnej liczby klik, ponieważ maksymalna klika musi być zawarta wśród wszystkich maksymalnych klik.
W zadaniu $k-$ kliki dane wejściowe to graf nieskierowany i liczba $k$ . Wyjściem jest klika z $k$ wierzchołków, jeśli taka istnieje, lub specjalna wartość wskazująca, że w przeciwnym razie nie ma $k$ -kliki. W niektórych odmianach tego problemu wynik powinien zawierać listę wszystkich klik o rozmiarze $k$ .
W problemie decyzyjnym kliki, dane wejściowe to graf nieskierowany i liczba $k$ , a wynikiem jest wartość logiczna : prawda, jeśli graf zawiera $k$ -klikę, a fałsz w przeciwnym razie.

Pierwsze cztery z tych problemów są ważne w zastosowaniach praktycznych. Problem decyzyjny kliki nie ma praktycznego znaczenia; jest sformułowana w ten sposób, aby zastosować teorię NP-zupełności do problemów znajdowania klik.

Problem klika i niezależny zestaw problemem są komplementarne: klika w $G$ jest niezależny zestaw na wykresie dopełniacza z $G$ i na odwrót. Dlatego też wiele wyników obliczeniowych można równie dobrze zastosować do obu problemów, a niektóre prace badawcze nie rozróżniają wyraźnie tych dwóch problemów. Jednak te dwa problemy mają różne właściwości w przypadku zastosowania do ograniczonych rodzin grafów. Na przykład, problem kliki może być rozwiązany w czasie wielomianowym dla grafów planarnych, podczas gdy problem zbioru niezależnego pozostaje NP-trudny na grafach planarnych.

Algorytmy

Znalezienie jednej maksymalnej kliki

Maksymalna klika, czasami nazywany włączenie maksymalnej, jest klika, która nie jest zawarta w większej kliki. Dlatego każda klika zawiera się w maksymalnej kliki. Maksymalna liczba klik może być bardzo mała. Wykres może zawierać klikę niemaksymalną z wieloma wierzchołkami oraz oddzielną klikę o rozmiarze 2, która jest maksymalna. Podczas gdy maksymalna (tj. największa) klika jest z konieczności maksymalna, odwrotność nie zachodzi. Istnieje kilka typów grafów, w których każda maksymalna klika jest maksymalna; są to uzupełnienia tych dobrze pokryte wykresami , w którym każda ilość niezależny zestaw jest maksymalne. Jednak inne wykresy mają maksymalne kliki, które nie są maksymalne.

Pojedynczą maksymalną klikę można znaleźć za pomocą prostego algorytmu zachłannego . Rozpoczynając od dowolnej kliki (na przykład dowolnego pojedynczego wierzchołka lub nawet pustego zbioru), powiększaj bieżącą klikę o jeden wierzchołek na raz, wykonując pętlę przez pozostałe wierzchołki wykresu. Dla każdego wierzchołka $v,$ który sprawdza ta pętla, dodaj $v$ do kliki, jeśli sąsiaduje z każdym wierzchołkiem, który już jest w klikie, i odrzuć $v w$ przeciwnym razie. Ten algorytm działa w czasie liniowym . Ze względu na łatwość znajdowania maksymalnych klik i ich potencjalny mały rozmiar, większą uwagę zwrócono na znacznie trudniejszy algorytmiczny problem znalezienia maksymalnej lub innej dużej kliki. Jednak niektóre badania w równoległych algorytmach badały problem znalezienia maksymalnej kliki. W szczególności, problem znalezienia leksykograficznie pierwszej maksymalnej kliki (tej znalezionej przez powyższy algorytm) okazał się kompletny dla klasy funkcji wielomianowych . Wynik ten sugeruje, że jest mało prawdopodobne, aby problem został rozwiązany w ramach równoległej klasy złożoności NC .

Kliki o stałym rozmiarze

Można sprawdzić, czy graf $G$ zawiera klikę $k-$ wierzchołków i znaleźć taką klikę, którą zawiera, używając algorytmu brute force . Algorytm ten bada każdy podgraf z $k$ wierzchołków i sprawdza, czy tworzy on klikę. Zajmuje czas $O (n k k 2)$ , wyrażony za pomocą notacji duże O . Dzieje się tak dlatego, że do sprawdzenia jest $O (n k)$ podgrafów, z których każdy ma $O (k 2)$ krawędzi, których obecność w $G$ musi być sprawdzona. Tak więc problem można rozwiązać w czasie wielomianowym, gdy $k$ jest stałą stałą. Jednakże, gdy $k$ nie ma stałej wartości, ale zamiast tego może się zmieniać jako część danych wejściowych problemu, czas jest wykładniczy.

Najprostszym nietrywialnym przypadkiem problemu znajdowania klik jest znalezienie trójkąta w grafie lub równoważne określenie, czy graf jest wolny od trójkątów . W grafie $G$ z $m$ krawędziami może występować co najwyżej $Θ(m 3/2)$ trójkątów (stosując notację dużego theta, aby wskazać, że to ograniczenie jest ciasne). Najgorszy przypadek dla tej formuły ma miejsce, gdy $G$ samo w sobie jest kliką. Dlatego algorytmy do wyliczenia wszystkich trójkątów muszą w najgorszym przypadku zająć co najmniej czas $Ω(m 3/2)$ (używając notacji big omega ), a znane są algorytmy, które pasują do tego ograniczenia czasowego. Na przykład Chiba i Nishizeki (1985) opisują algorytm, który sortuje wierzchołki w kolejności od najwyższego do najniższego, a następnie iteruje przez każdy wierzchołek $v$ na posortowanej liście, szukając trójkątów, które zawierają $v$ i nie zawierają żadnego poprzedniego wierzchołka w posortowanej liście. lista. Aby to zrobić, algorytm zaznacza wszystkich sąsiadów $v$ , przeszukuje wszystkie krawędzie związane z sąsiadem $v,$ generując trójkąt dla każdej krawędzi, która ma dwa zaznaczone punkty końcowe, a następnie usuwa znaczniki i usuwa $v$ z wykresu. Jak pokazują autorzy, czas działania tego algorytmu jest proporcjonalny do drzewiastości grafu (oznaczonej $a (G)$ ) pomnożonej przez liczbę krawędzi, czyli $O (m a (G))$ . Ponieważ lesistość wynosi co najwyżej $O (m 1/2)$ , algorytm działa w czasie $O (m 3/2)$ . Mówiąc bardziej ogólnie, wszystkie kliki $k$ -wierzchołków można wyliczyć za pomocą podobnego algorytmu, który zajmuje czas proporcjonalny do liczby krawędzi pomnożonych przez lesistość do potęgi $(k - 2 )$ . W przypadku grafów o stałej drzewie, takich jak grafy planarne (lub ogólnie grafy z dowolnej nietrywialnej rodziny mniejszych grafów zamkniętych ), algorytm ten zajmuje czas $O (m)$ , który jest optymalny, ponieważ jest liniowy pod względem wielkości danych wejściowych.

Jeśli ktoś pragnie tylko jednego trójkąta lub zapewnienia, że wykres jest wolny od trójkątów, możliwe są szybsze algorytmy. Jak zauważają Itai i Rodeh (1978) , wykres zawiera trójkąt wtedy i tylko wtedy, gdy jego macierz sąsiedztwa i kwadrat macierzy sąsiedztwa zawierają niezerowe wpisy w tej samej komórce. Dlatego techniki szybkiego mnożenia macierzy można zastosować do znalezienia trójkątów w czasie $O (n 2,376)$ . Alon, Yuster i Zwick (1994) zastosowali szybkie mnożenie macierzy w celu ulepszenia algorytmu $O (m 3/2)$ do znajdowania trójkątów do $O (m 1,41)$ . Algorytmy te oparte na szybkim mnożeniu macierzy zostały również rozszerzone o problemy znajdowania $k$ -klik dla większych wartości $k$ .

Lista wszystkich maksymalnych kliki

Zgodnie z wynikami Moona i Mosera (1965) każdy graf o $n$ -wierzchołkach ma co najwyżej $3 n /3$ maksymalnych klik. Można je wymienić za pomocą algorytmu Brona-Kerboscha , rekurencyjnej procedury z nawracaniem Brona i Kerboscha (1973) . Główny podprogram rekurencyjny tej procedury ma trzy argumenty: częściowo skonstruowaną (niemaksymalną) klikę, zbiór kandydujących wierzchołków, które można dodać do kliki, oraz inny zbiór wierzchołków, których nie należy dodawać (ponieważ prowadziłoby to do do kliki, która już została znaleziona). Algorytm próbuje dodać kandydujące wierzchołki jeden po drugim do częściowej kliki, wykonując rekurencyjne wywołanie dla każdego z nich. Po wypróbowaniu każdego z tych wierzchołków przenosi go do zestawu wierzchołków, których nie należy ponownie dodawać. Można wykazać, że warianty tego algorytmu mają najgorszy przypadek czasu działania $O (3 n /3)$ , pasujący do liczby klik, które mogą wymagać wykazania . Dlatego jest to najgorsze, optymalne rozwiązanie problemu wyliczenia wszystkich maksymalnych klik. Co więcej, algorytm Brona-Kerboscha jest powszechnie zgłaszany jako szybszy w praktyce niż jego alternatywy.

Jednak gdy liczba klik jest znacznie mniejsza niż jej najgorszy przypadek, inne algorytmy mogą być preferowane. Jak Tsukiyama i in. (1977) wykazali, że możliwe jest również wymienienie wszystkich maksymalnych klik na wykresie w czasie, który jest wielomianem na wygenerowaną klikę. Algorytm taki jak ich, w którym czas działania zależy od rozmiaru danych wyjściowych, nazywany jest algorytmem wrażliwym na dane wyjściowe . Ich algorytm opiera się na następujących dwóch obserwacjach, wiążących maksymalne kliki danego grafu $G$ z maksymalnymi klikami grafu $G \ v$ utworzonego przez usunięcie dowolnego wierzchołka $v$ z $G$ :

Dla każdej maksymalnej kliki $K$ z $G \ v$ , albo $K$ nadal tworzy maksymalną klikę w $G$ , albo $K ⋃ {v}$ tworzy maksymalną klikę w $G$ . Dlatego $G$ ma co najmniej tyle maksymalnych klik, co $G \ v$ .
Każda maksymalna klika w $G$ , która nie zawiera $v$ jest maksymalną kliką w $G \ v$ , a każda maksymalna klika w $G$ , która zawiera $v$ może być utworzona z maksymalnej kliki $K$ w $G \ v$ przez dodanie $v$ i usunięcie niesąsiadujących elementów z $v$ od $K$ .

Korzystając z tych obserwacji, mogą wygenerować wszystkie maksymalne kliki w $G$ za pomocą rekurencyjnego algorytmu, który arbitralnie wybiera wierzchołek $v,$ a następnie, dla każdej maksymalnej kliki $K$ w $G \ v$ , wyprowadza zarówno $K ,$ jak i klikę utworzoną przez dodanie $v$ do $K$ i usunięcie nie -sąsiedzi $v$ . Jednak niektóre kliki $G$ mogą być generowane w ten sposób z więcej niż jednej kliki rodzicielskiej $G \ v$ , więc eliminują duplikaty przez wypisanie kliki w $G$ tylko wtedy, gdy jej rodzic w $G \ v$ jest leksykograficznie maksimum spośród wszystkich możliwych kliki rodzicielskich. Na podstawie tej zasady pokazują, że wszystkie maksymalne kliki w $G$ mogą być generowane w czasie $O (mn)$ na klikę, gdzie $m$ to liczba krawędzi w $G,$ a $n$ to liczba wierzchołków. Chiba i Nishizeki (1985) poprawili to do $O(ma)$ na klikę, gdzie $a$ jest drzewnością danego wykresu. Makino i Uno (2004) zapewniają alternatywny algorytm wrażliwy na dane wyjściowe, oparty na szybkim mnożeniu macierzy. Johnson i Yannakakis (1988) wykazali, że możliwe jest nawet wymienienie wszystkich maksymalnych klik w porządku leksykograficznym z wielomianowym opóźnieniem na klikę. Jednak wybór porządkowania jest ważny dla skuteczności tego algorytmu: dla odwrotności tego porządku nie ma algorytmu wielomianowo-opóźniającego, chyba że P = NP .

Na podstawie tego wyniku można wyliczyć wszystkie maksymalne kliki w czasie wielomianowym dla rodzin grafów, w których liczba klik jest ograniczona wielomianem. Rodziny te obejmują akordowe wykresy , graf pełny , trójkąt wolne wykresy , interwał wykresy , wykresy ograniczonego boxicity i grafów planarnych . W szczególności grafy planarne mają $O (n)$ klik, o co najwyżej stałej wielkości, które mogą być wymienione w czasie liniowym. To samo dotyczy każdej rodziny grafów, która jest zarówno rzadka (mająca liczbę krawędzi co najwyżej stała razy liczba wierzchołków), jak i zamknięta w ramach operacji pobierania podgrafów.

Znajdowanie maksymalnych klik w dowolnych grafach

Możliwe jest znalezienie maksymalnej kliki lub liczby klik dowolnego grafu n -wierzchołkowego w czasie $O (3 n /3) = O (1.4422 n)$ przy użyciu jednego z algorytmów opisanych powyżej, aby $wypisać$ wszystkie maksymalne kliki w wykres i zwrócenie największego. Jednak dla tego wariantu problemu kliki możliwe są lepsze granice czasowe w najgorszym przypadku. Algorytm Tarjana i Trojanowskiego (1977) rozwiązuje ten problem w czasie $O (2 n /3) = O (1,2599 n)$ . Jest to schemat rekurencyjnego śledzenia wstecznego podobny do algorytmu Brona-Kerboscha , ale jest w stanie wyeliminować niektóre wywołania rekurencyjne, gdy można wykazać, że kliki znalezione w wywołaniu będą nieoptymalne. Jian (1986) poprawił czas do $O (2 0,304 n) = O (1,2346 n)$ , a Robson (1986) poprawił go do $O (2 0,276 n) = O (1,2108 n)$ czasu, kosztem większego wykorzystania przestrzeni . Algorytm Robsona łączy podobny schemat śledzenia wstecznego (z bardziej skomplikowaną analizą przypadków) oraz technikę programowania dynamicznego , w której optymalne rozwiązanie jest wstępnie obliczane dla wszystkich małych połączonych podgrafów grafu dopełnienia . Te częściowe rozwiązania są używane do skrócenia rekurencji z nawracaniem. Najszybszy znany dziś algorytm jest udoskonaloną wersją tej metody autorstwa Robsona (2001), która działa w czasie $O (2 0,249 n) = O (1,1888 n)$ .

Przeprowadzono również szeroko zakrojone badania nad algorytmami heurystycznymi do rozwiązywania problemów z maksymalną liczbą kliki bez gwarancji wykonania najgorszego przypadku, w oparciu o takie metody, jak branch and bound , lokalne wyszukiwanie , algorytmy zachłanne i programowanie z ograniczeniami . Niestandardowe metodologie obliczeniowe, które zostały zasugerowane w celu znalezienia klik, obejmują obliczanie DNA i adiabatyczne obliczenia kwantowe . Problem maksymalnej kliki był przedmiotem wyzwania implementacyjnego sponsorowanego przez DIMACS w latach 1992-1993 oraz zbioru wykresów wykorzystywanych jako punkty odniesienia dla wyzwania, który jest publicznie dostępny.

Specjalne klasy grafów

Na tym wykresie permutacji maksymalne kliki odpowiadają najdłuższym malejącym podciągom (4,3,1) i (4,3,2) permutacji definiującej.

Grafy planarne i inne rodziny grafów rzadkich zostały omówione powyżej: mają liniowo wiele maksymalnych klik o ograniczonej wielkości, które mogą być wymienione w czasie liniowym. W szczególności w przypadku grafów planarnych dowolna klika może mieć co najwyżej cztery wierzchołki, zgodnie z twierdzeniem Kuratowskiego .

Idealne grafy są definiowane przez własności , że ich liczba klik jest równa ich liczbie chromatycznej , i że ta równość zachodzi również w każdym z ich indukowanych podgrafów . W przypadku doskonałych grafów możliwe jest znalezienie maksymalnej kliki w czasie wielomianowym za pomocą algorytmu opartego na programowaniu półokreślonym . Jest to jednak metoda złożona i niekombinatoryczna, a dla wielu podklas doskonałych grafów opracowano wyspecjalizowane algorytmy znajdowania klik. Na wykresach dopełniacza z graf dwudzielny , König twierdzenie pozwala maksymalna klika problemem, który należy rozwiązać przy użyciu technik dopasowywania . W innej klasie doskonałych grafów, grafach permutacyjnych , maksymalna klika jest najdłuższym malejącym podciągiem permutacji definiującej graf i można ją znaleźć przy użyciu znanych algorytmów dla najdłuższego problemu podciągu malejącego. I odwrotnie, każdy przypadek najdłuższego malejącego problemu podciągu można równoważnie opisać jako problem znalezienia maksymalnej kliki w grafie permutacji. Nawet Pnueli i Lempel (1972) dostarczają alternatywnego algorytmu czasu kwadratowego dla maksymalnych klik w grafach porównywalności , szerszej klasy doskonałych grafów, która obejmuje grafy permutacji jako przypadek szczególny. W grafach akordowych maksymalne kliki można znaleźć, wymieniając wierzchołki w kolejności eliminacji i sprawdzając sąsiedztwo klik każdego wierzchołka w tej kolejności.

W niektórych przypadkach algorytmy te można rozszerzyć również na inne, niedoskonałe klasy grafów. Na przykład na wykresie kołowym sąsiedztwo każdego wierzchołka jest wykresem permutacyjnym, więc maksymalną klikę na wykresie kołowym można znaleźć, stosując algorytm grafu permutacyjnego do każdego sąsiedztwa. Podobnie w grafie dyskowym jednostkowym (ze znaną reprezentacją geometryczną) istnieje wielomianowy algorytm czasu dla maksymalnych klik oparty na zastosowaniu algorytmu dla uzupełnień grafów dwudzielnych do współdzielonych sąsiedztw par wierzchołków.

Algorytmiczny problem znajdowania maksymalnej kliki w losowym grafie zaczerpniętym z modelu Erdősa-Rényiego (w którym każda krawędź pojawia się z prawdopodobieństwem $1/2$ , niezależnie od pozostałych krawędzi) zasugerował Karp (1976) . Ponieważ maksymalna klika w losowym grafie ma wielkość logarytmiczną z dużym prawdopodobieństwem, można ją znaleźć metodą brute force w oczekiwanym czasie $2 O (log 2 n)$ . Jest to quasi-wielomianowa granica czasu . Chociaż liczba klik takich grafów jest zwykle bardzo zbliżona do $2 log 2 n$ , proste algorytmy zachłanne, jak również bardziej wyrafinowane techniki aproksymacji randomizowanej znajdują tylko kliki o rozmiarze $log 2 n$ , o połowę mniejszym . Liczba maksymalnych klik w takich grafach jest z dużym prawdopodobieństwem wykładnicza w $log 2 n$ , co zapobiega uruchamianiu metod wykazujących wszystkie maksymalne kliki w czasie wielomianowym. Ze względu na trudność tego problemu, kilku autorów zbadało problem zasadzonych klik, problem klik na losowych wykresach, które zostały rozszerzone przez dodanie dużych klik. Podczas gdy metody spektralne i programowanie półokreślone mogą wykrywać ukryte kliki o rozmiarze $Ω(\sqrt n)$ , nie są obecnie znane żadne algorytmy czasu wielomianowego wykrywające te o rozmiarze $o (\sqrt n)$ (wyrażone przy użyciu notacji little-o ).

Algorytmy aproksymacyjne

Kilku autorów rozważało algorytmy aproksymacyjne, które próbują znaleźć klikę lub niezależny zbiór, który, choć nie maksymalny, ma rozmiar tak bliski maksimum, jaki można znaleźć w czasie wielomianowym. Chociaż znaczna część tej pracy skupiała się na niezależnych zbiorach w grafach rzadkich, co nie ma sensu w przypadku problemu kliki komplementarnej, prowadzone były również prace nad algorytmami aproksymacyjnymi, które nie stosują takich założeń rzadkości.

Feige (2004) opisuje wielomianowy algorytm czasu, który znajduje klikę o rozmiarze $Ω((log n /log log n) 2)$ w każdym grafie, który ma liczbę kliki $Ω(n /log k n)$ dla dowolnej stałej $k$ . Używając tego algorytmu, gdy liczba klik danego grafu wejściowego wynosi od $n /log n$ do $n /log 3 n$ , przełączając się na inny algorytm Boppany i Halldórssona (1992) dla grafów o większej liczbie klik i wybierając dwu- Klika wierzchołków, jeśli oba algorytmy niczego nie znajdą, Feige dostarcza algorytm aproksymacyjny, który znajduje klikę z liczbą wierzchołków ze współczynnikiem $O(n (log log n) 2 /log 3 n)$ maksimum. Chociaż współczynnik aproksymacji tego algorytmu jest słaby, jest on jak dotąd najlepiej znany. Opisane poniżej wyniki dotyczące twardości aproksymacji sugerują, że nie może istnieć algorytm aproksymacji o współczynniku aproksymacji znacznie mniejszym niż liniowy.

Dolne granice

NP-zupełność

Instancja spełnialności 3-CNF (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) zredukowana do Clique. Zielone wierzchołki tworzą trójkę i odpowiadają satysfakcjonującemu przypisaniu.

Problem decyzyjny kliki jest NP-zupełny . Był to jeden z oryginalnych 21 problemów Richarda Karpa, pokazanych jako NP-zupełne w jego pracy z 1972 r. „Reducibility Among Combinatorial Problems”. Problem ten został również wspomniany w artykule Stephena Cooka , wprowadzającym teorię problemów NP-zupełnych. Ze względu na trudność problemu decyzyjnego, problem znalezienia maksymalnej kliki jest również NP-trudny. Gdyby można było go rozwiązać, można by również rozwiązać problem decyzyjny, porównując rozmiar maksymalnej kliki z parametrem rozmiaru podanym jako dane wejściowe w problemie decyzyjnym.

Dowód NP-zupełności Karpa jest redukcją wiele-jeden z problemu spełnialności logicznej . Opisuje, jak tłumaczyć formuły Boole'a w koniunkcyjnej postaci normalnej (CNF) na równoważne przypadki problemu maksymalnej kliki. Spełnialność z kolei została udowodniona NP-zupełna w twierdzeniu Cooka-Levina . Z danej formuły CNF Karp tworzy wykres, który ma wierzchołek dla każdej pary $(v, c)$ , gdzie $v$ jest zmienną lub jej negacją $ic$ jest klauzulą we wzorze zawierającą $v$ . Dwa z tych wierzchołków są połączone krawędzią, jeśli reprezentują zgodne przypisania zmiennych dla różnych klauzul. Oznacza to, że krawędź od $(v, c)$ do $(u, d)$ , gdy $C \neq D$ i $U$ i $V,$ nie są wzajemnie zaprzeczenia. Jeśli $k$ oznacza liczbę klauzul we wzorze CNF, to kliki $k-$ wierzchołków na tym wykresie reprezentują spójne sposoby przypisywania wartości prawdy do niektórych jego zmiennych w celu spełnienia formuły. Dlatego formuła jest spełnialna wtedy i tylko wtedy, gdy istnieje klika $k-$ wierzchołków.

Niektóre problemy NP-zupełne (takie jak problem komiwojażera w grafach planarnych ) można rozwiązać w czasie wykładniczym w funkcji podliniowej parametru wielkości wejściowej $n$ , znacznie szybszym niż przeszukiwanie siłowe. Jednak jest mało prawdopodobne, aby takie podwykładnicze ograniczenie czasowe było możliwe dla problemu kliki w dowolnych grafach, ponieważ sugerowałoby to podobnie podwykładnicze ograniczenia dla wielu innych standardowych problemów NP-zupełnych.

Złożoność obwodu

Obwód monotoniczny do wykrywania

k-

kliki na wykresie

n

-wierzchołkowym dla

k = 3

i

n = 4

. Każde wejście do obwodu koduje obecność lub brak określonej (czerwonej) krawędzi na wykresie. Układ wykorzystuje jedną wewnętrzną bramkę i do wykrywania każdej potencjalnej

k-

kliki.

Trudność obliczeniowa problemu kliki doprowadziła do jego wykorzystania do udowodnienia kilku dolnych granic złożoności obwodów . Istnienie kliki o danym rozmiarze jest właściwością grafu monotonicznego , co oznacza, że jeśli klika istnieje w danym grafie, będzie istniała w każdym supergrafie . Ponieważ ta właściwość jest monotoniczna, musi istnieć obwód monotoniczny, wykorzystujący tylko bramki i lub bramki , aby rozwiązać problem decyzyjny kliki dla danego stałego rozmiaru kliki. Jednak można udowodnić, że rozmiar tych obwodów jest super-wielomianową funkcją liczby wierzchołków i rozmiaru kliki, wykładniczą w pierwiastku sześciennym liczby wierzchołków. Nawet jeśli dozwolona jest niewielka liczba bramek NOT , złożoność pozostaje superwielomianowa. Dodatkowo, głębokość obwodu monotonicznego dla problemu kliki używającego bramek ograniczonego wachlarza musi być co najmniej wielomianem w rozmiarze kliki.

Złożoność drzewa decyzyjnego

Proste drzewo decyzyjne do wykrywania obecności 3-kliki w grafie 4-wierzchołkowym. Wykorzystuje do 6 pytań w formie „Czy istnieje czerwona krawędź?”, dopasowując optymalne ograniczenie n ( n − 1)/2.

Złożoność drzewa decyzyjnego (deterministycznego) wyznaczania właściwości grafu to liczba pytań w postaci „Czy istnieje krawędź między wierzchołkiem $u$ a wierzchołkiem $v$ ?” na które należy odpowiedzieć w najgorszym przypadku, aby określić, czy graf ma określoną właściwość. Oznacza to, że jest to minimalna wysokość logicznego drzewa decyzyjnego dla problemu. Jest $n (n - 1)/2$ możliwych pytań, które można zadać. Dlatego dowolna właściwość grafu może być określona za pomocą co najwyżej $n (n - 1)/2$ pytań. Możliwe jest również zdefiniowanie losowej i kwantowej złożoności drzewa decyzyjnego właściwości, oczekiwanej liczby pytań (dla danych wejściowych najgorszego przypadku), na które algorytm randomizowany lub kwantowy musi odpowiedzieć, aby poprawnie określić, czy dany graf ma tę właściwość .

Ponieważ właściwość zawierania kliki jest monotoniczna, jest ona objęta hipotezą Aanderaa-Karp-Rosenberg , która stwierdza, że złożoność deterministycznego drzewa decyzyjnego określająca dowolną nietrywialną właściwość grafu monotonicznego wynosi dokładnie $n (n - 1)/2$ . W przypadku dowolnych właściwości grafu monotonicznego to przypuszczenie pozostaje nieudowodnione. Jednak dla deterministycznych drzew decyzyjnych, a dla każdego $k$ w zakresie $2 \leq k \leq n$ , własność zawierający $k$ -clique Wykazano, że drzewo decyzyjne złożoność dokładnie $n (n - 1) / 2$ przez Bollobás (1976) . Deterministyczne drzewa decyzyjne wymagają również rozmiaru wykładniczego do wykrywania klik lub dużego wielomianu do wykrywania klik o ograniczonym rozmiarze.

Hipoteza Aanderaa-Karpa-Rosenberga również mówi, że złożoność randomizowanego drzewa decyzyjnego nietrywialnych funkcji monotonicznych wynosi $Θ(n 2)$ . Przypuszczenie ponownie pozostaje nieudowodnione, ale zostało rozwiązane ze względu na właściwość zawierania kliki $k$ dla $2 \leq k \leq n$ . Wiadomo, że ta własność ma randomizowaną złożoność drzewa decyzyjnego $Θ(n 2)$ . W przypadku kwantowych drzew decyzyjnych najbardziej znanym dolnym ograniczeniem jest $Ω(n)$ , ale nie jest znany żaden algorytm dopasowywania dla przypadku $k \geq 3$ .

Nieusuwalność przy stałym parametrze

Sparametryzowana złożoność to teoretyczne badanie złożoności problemów, które są naturalnie wyposażone w mały parametr całkowity $k$ i dla których problem staje się trudniejszy wraz ze wzrostem $k$ , na przykład znajdowanie $k$ -klik na wykresach. Mówi się, że problem jest wykonalny ze stałym parametrem, jeśli istnieje algorytm do jego rozwiązania na danych wejściowych o rozmiarze $n$ oraz funkcja $f$ , taka, że algorytm działa w czasie $f (k) n O (1)$ . Oznacza to, że jest to stałoparametrowe wykonalne, jeśli można je rozwiązać w czasie wielomianu dla dowolnej stałej wartości $k,$ a ponadto, jeśli wykładnik wielomianu nie zależy od $k$ .

Aby znaleźć kliki $k$ -wierzchołków, algorytm wyszukiwania brute force ma czas działania $O(n k k 2)$ . Ponieważ wykładnik $n$ zależy od $k$ , algorytm ten nie jest wykonalny dla stałych parametrów. Chociaż można to ulepszyć przez szybkie mnożenie macierzy, czas wykonania nadal ma wykładnik liniowy w $k.$ Tak więc, chociaż czas wykonania znanych algorytmów dla problemu klik jest wielomianowy dla dowolnego ustalonego $k$ , algorytmy te nie wystarczą dla stałego parametru ustępliwość. Downey i Fellows (1995) zdefiniowali hierarchię problemów sparametryzowanych, hierarchię W, co do których przypuszczali, że nie mają algorytmów o stałej parametryzacji. Udowodnili, że niezależny zbiór (lub równoważnie klika) jest trudny dla pierwszego poziomu tej hierarchii, W[1] . Tak więc, zgodnie z ich przypuszczeniami, klika nie ma możliwego do realizacji algorytmu o stałym parametrze. Co więcej, wynik ten stanowi podstawę dla dowodów W[1]-twardości wielu innych problemów, a zatem służy jako analogia do twierdzenia Cooka-Levina dla sparametryzowanej złożoności.

Chen i in. (2006) wykazali, że znalezienie $k$ -wierzchołków nie może być wykonane w czasie $n o (k),$ chyba że hipoteza czasu wykładniczego zawiedzie. Ponownie dostarcza to dowodu na to, że nie jest możliwy żaden wykonalny algorytm o stałych parametrach.

Chociaż problemy z wypisaniem maksymalnych klik lub znalezieniem maksymalnych klik prawdopodobnie nie będą wykonalne dla stałych parametrów z parametrem $k$ , mogą być wykonalne dla stałych parametrów dla innych parametrów o złożoności instancji. Na przykład wiadomo, że oba problemy są rozwiązywalne za pomocą stałych parametrów, gdy są sparametryzowane przez degenerację grafu wejściowego.

Twardość aproksymacji

Wykres relacji zgodności między 2-bitowymi próbkami 3-bitowych ciągów dowodowych. Każda maksymalna klika (trójkąt) na tym wykresie reprezentuje wszystkie sposoby próbkowania pojedynczego 3-bitowego ciągu. Dowodem nieprzystosowalności problemu kliki są indukowane podgrafy analogicznie zdefiniowanych grafów dla większej liczby bitów.

Słabe wyniki sugerujące, że problem kliki może być trudny do przybliżenia, były znane od dawna. Garey i Johnson (1978) zaobserwowali, że ponieważ liczba klik przyjmuje małe wartości całkowite i jest NP-trudna do obliczenia, nie może mieć pełnego wielomianowego schematu aproksymacji . Gdyby dostępne było zbyt dokładne przybliżenie, zaokrąglenie jego wartości do liczby całkowitej dałoby dokładną liczbę kliki. Jednak niewiele więcej było wiadomo aż do początku lat 90., kiedy kilku autorów zaczęło łączyć aproksymację maksymalnych klik i probabilistycznie sprawdzalnych dowodów . Użyli tych połączeń do udowodnienia twardości wyników aproksymacji dla problemu maksymalnej kliki. Po wielu ulepszeniach tych wyników wiadomo, że dla każdej liczby rzeczywistej $ε > 0$ , nie może być algorytmu czasu wielomianowego, który aproksymuje maksymalną klikę do współczynnika lepszego niż $O (n 1 - ε)$ , chyba że P = NP .

Zgrubna idea tych wyników nieprzybliżeniowości polega na utworzeniu grafu, który reprezentuje probabilistycznie sprawdzalny system dowodowy dla problemu NP-zupełnego, takiego jak problem spełnialności Boole'a. W probabilistycznie sprawdzalnym systemie dowodowym dowód jest reprezentowany jako ciąg bitów. Wystąpienie problemu spełnialności powinno mieć ważny dowód wtedy i tylko wtedy, gdy jest spełnialny. Dowód jest sprawdzany przez algorytm, który po obliczeniu danych wejściowych problemu spełnialności w czasie wielomianowym wybiera do zbadania niewielką liczbę losowo wybranych pozycji ciągu dowodowego. W zależności od tego, jakie wartości zostaną znalezione w tej próbce bitów, kontroler zaakceptuje lub odrzuci dowód, nie patrząc na resztę bitów. Fałszywe negatywy są niedozwolone: ważny dowód musi być zawsze akceptowany. Jednak czasami nieważny dowód może być błędnie zaakceptowany. Dla każdego nieważnego dowodu prawdopodobieństwo, że osoba sprawdzająca go zaakceptuje, musi być niskie.

Aby przekształcić probabilistycznie sprawdzalny system dowodowy tego typu w problem klikowy, tworzy się graf z wierzchołkiem dla każdego możliwego przebiegu akceptującego kontrolera dowodu. Oznacza to, że wierzchołek jest zdefiniowany przez jeden z możliwych losowych wyborów zestawów pozycji do zbadania oraz przez wartości bitowe dla tych pozycji, które spowodowałyby, że kontroler zaakceptowałby dowód. Może być reprezentowany przez częściowe słowo z 0 lub 1 na każdej badanej pozycji i znakiem wieloznacznym na każdej pozostałej pozycji. Dwa wierzchołki sąsiadują ze sobą, na tym wykresie, jeśli odpowiadające im dwa przebiegi akceptujące widzą te same wartości bitów w każdej pozycji, którą obaj badają. Każdy (ważny lub nieważny) ciąg dowodowy odpowiada kliki, zbiorowi przebiegów akceptujących, które widzą ten ciąg dowodowy, iw ten sposób powstają wszystkie maksymalne kliki. Jedna z tych klik jest duża wtedy i tylko wtedy, gdy odpowiada ciągowi dowodowemu, który akceptuje wiele osób sprawdzających dowody. Jeśli oryginalna instancja spełnialności jest satisfiable, będzie miała poprawny ciąg dowodowy, który jest akceptowany przez wszystkie przebiegi programu sprawdzającego, a ten ciąg będzie odpowiadał dużej kliki na grafie. Jednakże, jeśli oryginalna instancja nie jest satysfakcjonująca, to wszystkie łańcuchy dowodu są nieważne, każdy łańcuch dowodu ma tylko niewielką liczbę przebiegów sprawdzania, które błędnie go akceptują, a wszystkie kliki są małe. Dlatego, gdyby można było rozróżnić w czasie wielomianowym grafy z dużymi klikami od grafów, w których wszystkie kliki są małe, lub gdyby można było dokładnie aproksymować problem kliki, to zastosowanie tego przybliżenia do grafów generowanych z instancji spełnialności pozwoliłoby na spełnianie instancji należy odróżnić od niezadowalających przypadków. Nie jest to jednak możliwe, chyba że P = NP.

Uwagi

Bibliografia

Ankiety i podręczniki

Arora, Sanjeev ; Barak, Boaz (2009), Złożoność obliczeniowa: nowoczesne podejście , Cambridge University Press, ISBN 978-0-521-42426-4.
Blair, Jean RS; Peyton, Barry (1993), „Wprowadzenie do grafów akordowych i drzew klikowych”, Teoria grafów i obliczenia macierzy rzadkich , IMA tom. Matematyka. Appl., 56 , Springer, New York, s. 1-29, doi : 10.1007/978-1-4613-8369-7_1 , MR 1320296.
Bomze, komunikator internetowy; Budinich, M.; Pardalos, PM; Pelillo, M. (1999), „Maksymalny problem kliki”, Handbook of Combinatorial Optimization , 4 , Kluwer Academic Publishers, s. 1-74, CiteSeerX 10.1.1.48.4074.
Cormen, Thomas H .; Leiserson, Charles E. ; Rivest, Ronald L .; Stein, Clifford (2001), „34.5.1 Problem kliki”, Wprowadzenie do algorytmów (2nd ed.), MIT Press i McGraw-Hill, s. 1003–1006, ISBN 0-262-03293-7.
Downey, RG; Fellows, MR (1999), Sparametryzowana złożoność , Springer-Verlag , ISBN 0-387-94883-X.
Golumbic, MC (1980), algorytmiczna teoria grafów i doskonałe wykresy , informatyka i matematyka stosowana, prasa akademicka , ISBN 0-444-51530-5.
Grötschel, M .; Lovász, L .; Schrijver, A. (1988), "9.4 Coloring Perfect Graphs", algorytmy geometryczne i optymalizacja kombinatoryczna , algorytmy i kombinatoryka , 2 , Springer-Verlag , s. 296-298, ISBN 0-387-13624-X.
Gutin, G. (2004), „5.3 Niezależne zbiory i kliki”, w Gross, JL; Yellen, J. (red.), Podręcznik teorii grafów , Matematyka dyskretna i jej zastosowania , CRC Press, s. 389-402, ISBN 978-1-58488-090-5.
Mugge, Ingo; Rarey, Matthias (2001), "Dokowanie i punktacja małych cząsteczek", Recenzje w chemii obliczeniowej , 17 : 1-60, doi : 10.1002/0471224413.ch1 , ISBN 9780471398455.
Komitet National Research Council on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry , National Academies Press, doi : 10.17226/4886 , ISBN 978-0-309-05097-5.
Pelillo, Marcello (2009), "Heurystyki dla maksymalnej kliki i niezależnego zbioru", Encyklopedia Optymalizacji , Springer, pp. 1508-1520, doi : 10.1007/978-0-387-74759-0_264.
Plummer, Michael D. (1993), „Dobrze pokryte wykresy: ankieta” , Quaestiones Mathematicae , 16 (3): 253-287, doi : 10.1080/16073606.1993.9631737 , MR 1254158.
Sipser, M. (1996), Wprowadzenie do teorii obliczeń , International Thompson Publishing , ISBN 0-534-94728-X.
Skiena, Steven S. (2009), Podręcznik projektowania algorytmów (2nd ed.), Springer, ISBN 978-1-84800-070-4.
Valiente, Gabriel (2002), "Rozdział 6: Clique, Independent Set i Vertex Cover", Algorytmy na drzewach i wykresach , Springer, pp. 299-350, doi : 10.1007/978-3-662-04921-1_6.
Wasserman, Stanley ; Faust, Katherine (1994), Analiza sieci społecznych: metody i zastosowania , Analiza strukturalna w naukach społecznych, 8 , Cambridge University Press, s. 276, ISBN 978-0-521-38707-1.

Popularna prasa

Kolata, Gina (26 czerwca 1990), "W szale matematyka wkracza w erę poczty elektronicznej" , The New York Times.

Artykuły naukowe

Abello, J.; Pardalos, PM; Resende, MGC (1999), "O problemach maksymalnej kliki w bardzo dużych grafach" (PDF) , w Abello, J.; Vitter, J. (red.), Algorytmy pamięci zewnętrznej , Seria DIMACS na temat matematyki dyskretnej i informatyki teoretycznej, 50 , American Mathematical Society , s. 119-130, ISBN 0-8218-1184-3.
Alon, N .; Boppana, R. (1987), "złożoność obwodu monotone funkcji logicznych", Combinatorica , 7 (1): 1-22, doi : 10.1007/BF02579196 , S2CID 17397273.
Alon, N .; Krivelevich, M.; Sudakov, B. (1998), „Znalezienie dużej ukrytej kliki w losowym wykresie”, Struktury i algorytmy losowe , 13 (3-4): 457-466, doi : 10.1002/(SICI) 1098-2418 (199810/12 )13:3/4<457::AID-RSA14>3.0.CO;2-W.
Alon, N .; Yuster, R.; Zwick, U. (1994), "Znajdowanie i liczenie danych cykli długości", Proceedings of the 2nd European Symposium on Algorithms , Utrecht, Holandia , pp 354-364.
Amano, Kazuyukiego; Maruoka, Akira (2005), „Dolna granica superwielomianu dla obwodu obliczającego funkcję klik z co najwyżej $(1/6) log log N$ bramkami negacji”, SIAM Journal on Computing , 35 (1): 201-216, doi : 10.1137/S0097539701396959 , MR 2178806.
Arora, Sanjeev ; Lund, Carsten ; Motwani, Rajeev ; Sudan, Madhu ; Szegedy, Mario (1998), „Weryfikacja dowodu i twardość problemów aproksymacji”, Journal of the ACM , 45 (3): 501-555, doi : 10.1145/278298.278306 , S2CID 8561542 , ECCC TR98-008. Pierwotnie zaprezentowany na Sympozjum Podstaw Informatyki w 1992 roku , doi : 10.1109/SFCS.1992.267823 .
Arora, S .; Safra, S. (1998), "Probabilistyczna kontrola dowodów: nowa charakterystyka NP", Journal of the ACM , 45 (1): 70-122, doi : 10.1145/273865.273901 , S2CID 751563. Pierwotnie zaprezentowany na Sympozjum Podstaw Informatyki w 1992 roku , doi : 10.1109/SFCS.1992.267824 .
Balas, E.; Yu, CS (1986), „Znalezienie maksymalnej kliki w dowolnym wykresie”, SIAM Journal on Computing , 15 (4): 1054-1068, doi : 10.1137/0215075.
Barrow, H.; Burstall, R. (1976), „Izomorfizm podgrafu, dopasowywanie struktur relacyjnych i maksymalne kliki”, listy przetwarzania informacji , 4 (4): 83-84, doi : 10.1016/0020-0190 (76) 90049-1.
Battiti, R.; Protasi, M. (2001), "Reaktywne wyszukiwanie lokalne dla maksymalnego problemu kliki", Algorithmica , 29 (4): 610-637, doi : 10.1007/s004530010074 , S2CID 1800512.
Bollobás, Béla (1976), „Pełne podgrafy są nieuchwytne”, Journal of Combinatorial Theory , Series B, 21 (1): 1-7, doi : 10.1016/0095-8956(76)90021-6 , ISSN 0095-8956.
Boppana, R.; Halldórsson, MM (1992), "Aproksymowanie maksymalnych niezależnych zbiorów przez wykluczenie podgrafów", BIT Numerical Mathematics , 32 (2): 180-196, doi : 10.1007/BF01994876 , S2CID 123335474.
Bron, C.; Kerbosch, J. (1973), „Algorytm 457: znalezienie wszystkich klik nieskierowanego wykresu”, Komunikacja ACM , 16 (9): 575-577, doi : 10.1145/362342.362367 , S2CID 13886709.
Carraghan, R.; Pardalos, PM (1990), „Dokładny algorytm dla maksymalnego problemu kliki”, Operations Research Letters , 9 (6): 375-382, doi : 10.1016/0167-6377 (90) 90057-C.
Cazals, F.; Karande, C. (2008), „Notatka o problemie zgłaszania maksymalnych klik”, Theoretical Computer Science , 407 (1): 564-568, doi : 10.1016/j.tcs.2008.05.010.
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Strong computational lower bounds via parameterized complex", Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
Chiba, N.; Nishizeki, T. (1985), "Algorytmy arboricity i podgrafów", SIAM Journal on Computing , 14 (1): 210-223, doi : 10.1137/0214017.
Childs, AM; Farhi, E.; Goldstone, J .; Gutmann, S. (2002), "Finding cliques by quantum adiabatic evolution", Quantum Information and Computation , 2 (3): 181-191, arXiv : quant-ph/0012104 , Bibcode : 2000quant.ph.12104C , doi : 10.26421 /QIC2.3 , S2CID 33643794.
Childs, AM; Eisenberg, JM (2005), "Algorytmy kwantowe do znajdowania podzbiorów", Informacje i obliczenia kwantowe , 5 (7): 593-604, arXiv : quant-ph/0311038 , Bibcode : 2003quant.ph.11038C , doi : 10.26421/QIC5 .7 , S2CID 37556989.
Clark, Brent N.; Colbourn, Charles J .; Johnson, David S. (1990), "Wykresy dyskowe jednostkowe", Matematyka dyskretna , 86 (1-3): 165-177, doi : 10.1016/0012-365X(90)90358-O
Cook, SA (1971), "Złożoność procedur dowodzenia twierdzeń" , Proc. III Sympozjum ACM z Teorii Informatyki , s. 151-158, doi : 10.1145/800157.805047 , S2CID 7573663.
Cook, Stephen A. (1985), "Taksonomia problemów z szybkimi algorytmami równoległymi", Informacja i kontrola , 64 (1-3): 2-22, doi : 10.1016/S0019-9958 (85) 80041-3 , MR 0837088.
Dzień, William HE; Sankoff, David (1986), "złożoność obliczeniowa wnioskowania phylogenies przez kompatybilność" Systematic Zoology , 35 (2): 224-229, doi : 10.2307/2413432 , JSTOR 2413432.
Downey, RG; Stypendyści, MR (1995), „Fixed-parameter tractability and kompletność. II. Na kompletność dla W [1]”, Informatyka teoretyczna , 141 (1-2): 109-131, doi : 10.1016/0304-3975 (94 )00097-3.
Eisenbrand, F.; Grandoni, F. (2004), "O złożoności kliki o stałych parametrach i zbioru dominującego", Informatyka teoretyczna , 326 (1-3): 57-67, doi : 10.1016/j.tcs.2004.05.09.
Eppsteina, Dawida ; Löfflera, Maartena; Strash, Darren (2013), „Listing all maximal cliques in large sparse real-world graphs in near the optimum time”, Journal of Experimental Algorithmics , 18 (3): 3.1, arXiv : 1103.0318 , doi : 10.1145/2543629 , S2CID 47515491.
Erdős, Paul ; Szekeres, George (1935), „kombinatoryczny problem w geometrii” (PDF) , Compositio Mathematica , 2 : 463-470.
Nawet, S .; Pnueli, A .; Lempel, A. (1972), "wykresy permutacji i wykresy przechodnie", Journal of the ACM , 19 (3): 400-410, doi : 10.1145/321707.321710 , S2CID 9501737.
Fahle, T. (2002), „Prosty i szybki: Poprawa algorytmu branch-and-bound dla maksymalnej kliki”, Proc. 10. Europejskie Sympozjum Algorytmów , Lecture Notes in Computer Science, 2461 , Springer-Verlag, s. 47-86, doi : 10.1007/3-540-45749-6_44 , ISBN 978-3-540-44180-9.
Feige, U. (2004), „Aproksymowanie maksymalnej kliki przez usunięcie podgrafów”, SIAM Journal on Discrete Mathematics , 18 (2): 219-225, doi : 10.1137/S089548010240415X.
Feige, U .; Goldwasser, S .; Lovász, L .; Safra, S ; Szegedy, M. (1991), "Aproksymacja klika jest prawie NP-kompletna", Proc. 32. sympozjum IEEE o podstawach informatyki , s. 2–12, doi : 10.1109/SFCS.1991.185341 , ISBN 0-8186-2445-0, S2CID 46605913.
Feige, U .; Krauthgamer, R. (2000), „Znalezienie i certyfikacja dużej ukrytej kliki w półlosowym wykresie”, Struktury i algorytmy losowe , 16 (2): 195-208, doi : 10.1002/(SICI)1098-2418(200003)16 :2<195::AID-RSA5>3.0.CO;2-A.
Frank, Ove; Strauss, David (1986), „Wykresy Markowa”, Journal of the American Statistical Association , 81 (395): 832-842, doi : 10.2307/2289017 , JSTOR 2289017 , MR 0860518.
Garey, MR ; Johnson, DS (1978) " " silnych "Wyniki NP kompletności motywacja, przykłady i skutki", Journal of the ACM , 25 (3): 499-508, doi : 10,1145 / 322077,322090 , S2CID 18371269.
Garey, MR ; Johnsona, DS ; Stockmeyer, L. (1976), "Niektóre uproszczone problemy z wykresem NP-zupełnym", Informatyka teoretyczna , 1 (3): 237-267, doi : 10.1016/0304-3975 (76) 90059-1 , MR 0411240.
Gavril, F. (1973), „Algorytmy dla maksymalnej kliki i maksymalnego niezależnego zestawu wykresu kołowego”, Sieci , 3 (3): 261-273, doi : 10.1002/net.3230030305.
Goldmann, M.; Håstad, J. (1992), „Prosta dolna granica dla monotonnej kliki przy użyciu gry komunikacyjnej” (PDF) , Information Processing Letters , 41 (4): 221-226, CiteSeerX 10.1.1.185.3065 , doi : 10.1016/0020 -0190(92)90184-W.
Gröger, Hans Dietmar (1992), „O randomizowanej złożoności właściwości wykresu monotonicznego” (PDF) , Acta Cybernetica , 10 (3): 119-127 , pobrane 2009-10-02
Grosso, A.; Locatelli, M.; Della Croce, F. (2004), "Łączenie swapów i wag węzłów w adaptacyjnym chciwym podejściu do problemu maksymalnej kliki", Journal of Heuristics , 10 (2): 135-152, doi : 10.1023/B: HEUR.0000026264.51747. 7f , S2CID 40764225.
Halldórsson, MM (2000), "Aproksymacje Weighted Independent Set and Hereditary Subset Problems", Journal of Graph Algorithms and Applications , 4 (1): 1-16, doi : 10.7155/jgaa.00020.
Hamzaoglu, I.; Patel, JH (1998), "Algorytmy zagęszczania zestawu testowego dla układów kombinacyjnych", Proc. 1998 Międzynarodowa konferencja IEEE/ACM na temat projektowania wspomaganego komputerowo , s. 283–289, doi : 10.1145/288548.288615 , S2CID 12258606.
Harary, F .; Ross, IC (1957), "Procedura wykrywania kliki przy użyciu macierzy grupowej", Socjometria , American Sociological Association, 20 (3): 205-215, doi : 10.2307/2785673 , JSTOR 2785673 , MR 0110590.
Håstad, J. (1999), „Klik jest trudny do przybliżenia w zakresie $n 1 - ε$ ”, Acta Mathematica , 182 (1): 105-142, doi : 10.1007/BF02392825.
Impagliazzo, R .; Paturi, R.; Zane, F. (2001), „Które problemy mają silnie wykładniczą złożoność?”, Journal of Computer and System Sciences , 63 (4): 512-530, doi : 10.1006/jcss.2001.1774.
Itai, A.; Rodeh, M. (1978), „Znalezienie minimalnego obwodu na wykresie”, SIAM Journal on Computing , 7 (4): 413-423, doi : 10.1137/0207033.
Jerrum, M. (1992), „Duże kliki wymykają się procesowi Metropolis”, Struktury i algorytmy losowe , 3 (4): 347-359, doi : 10.1002/rsa.3240030402.
Jian, T (1986), " Algorytm $O (2 0,304 n)$ do rozwiązywania problemu maksymalnego niezależnego zestawu", IEEE Transactions on Computers , IEEE Computer Society, 35 (9): 847-851, doi : 10.1109/TC.1986.1676847 , ISSN 0018-9340.
Johnsona, DS ; Sztuczka, MA , wyd. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 11-13 października 1993 , Seria DIMACS in Discrete Mathematics and Theoretical Computer Science, 26 , American Mathematical Society , ISBN 0-8218-6609-5.
Johnsona, DS ; Yannakakis, M. (1988), „O generowaniu wszystkich maksymalnych niezależnych zbiorów”, Listy przetwarzania informacji , 27 (3): 119-123, doi : 10.1016/0020-0190 (88) 90065-8.
Karp, Richard M. (1972), „Redukcyjność wśród problemów kombinatorycznych”, w Miller, RE; Thatcher, JW (red.), Complexity of Computer Computations (PDF) , New York: Plenum , s. 85-103, zarchiwizowane z oryginału (PDF) dnia 2011-06-29 , pobrane 17.12.2009.
Karp, Richard M. (1976), "Analiza probabilistyczna niektórych kombinatorycznych problemów wyszukiwania", w Traub, JF (red.), Algorytmy i złożoność: Nowe kierunki i najnowsze wyniki , New York: Academic Press , s. 1-19.
Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), "Skuteczne lokalne wyszukiwanie problemu maksymalnej kliki", Information Processing Letters , 95 (5): 503-511, doi : 10.1016/j.ipl.2005.05.010.
Khot, S. (2001), „Poprawione wyniki nieprzybliżeniowości dla MaxClique, liczba chromatyczna i przybliżone kolorowanie wykresu”, Proc. 42. sympozjum IEEE Podstawy Informatyki , s. 600–609, doi : 10.1109/SFCS.2001.959936 , ISBN 0-7695-1116-3, S2CID 11987483.
Kloks, T.; Kratsch, D.; Müller, H. (2000), „Wyszukiwanie i liczenie małych podgrafów indukowanych efektywnie”, Information Processing Letters , 74 (3-4): 115-121, doi : 10.1016/S0020-0190(00)00047-8.
Konc, J.; Janežič, D. (2007), „Ulepszony algorytm gałęzi i wiązania dla maksymalnego problemu kliki” (PDF) , MATCH Communications in Mathematical and Computer Chemistry , 58 (3): 569-590. Kod źródłowy
Kuhl, FS; Crippen, GM; Friesen, DK (1983), "Algorytm kombinatoryczny do obliczania wiązania liganda", Journal of Computational Chemistry , 5 (1): 24-34, doi : 10.1002/jcc.540050105 , S2CID 122923018.
Lagarias, Jeffrey C .; Shor, Peter W. (1992), „przypuszczenie kostki płytek Kellera jest fałszywe w dużych wymiarach”, Biuletyn Amerykańskiego Towarzystwa Matematycznego , New Series , 27 (2): 279-283, arXiv : math/9210222 , doi : 10.1090 /S0273-0979-1992-00318-X , MR 1155280 , S2CID 6390600.
Lipton, RJ ; Tarjan, RE (1980), "Zastosowania twierdzenia o separatorze planarnym", SIAM Journal on Computing , 9 (3): 615-627, doi : 10.1137/0209046 , S2CID 12961628.
Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), „Towards maximum niezależnych zbiorów na masywnych grafach”, Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015) , Proceedings of the VLDB Endowment, 8 , s. 2122–2133, doi : 10.14778 /2831360.2831366 , hdl : 10138/157292.
Luce, R. Duncan ; Perry, Albert D. (1949), „Metoda analizy macierzy struktury grupy”, Psychometrika , 14 (2): 95-116, doi : 10.1007/BF02289146 , hdl : 10.1007/BF02289146 , PMID 18152948 , S2CID 16186758.
Mackey, John (2002), "kostka kafelki wymiaru ósmego bez dzielenia się twarzami", Geometria dyskretna i obliczeniowa , 28 (2): 275-279, doi : 10.1007/s00454-002-2801-9 , MR 1920144.
Magniez, Fryderyk; Śanta, Miklos; Szegedy, Mario (2007), "Algorytmy kwantowe dla problemu trójkąta", SIAM Journal on Computing , 37 (2): 413-424, arXiv : quant-ph/0310134 , doi : 10.1137/050643684 , S2CID 594494.
Makino, K.; Uno, T. (2004), „Nowe algorytmy wyliczania wszystkich maksymalnych klik”, Algorithm Theory: SWAT 2004 (PDF) , Lecture Notes in Computer Science, 3111 , Springer-Verlag , s. 260–272, CiteSeerX 10.1.1.138. 705 , doi : 10.1007/978-3-540-27810-8_23.
Meka, Raghu; Potechin, Aaron; Wigderson, Avi (2015), „Sum-of-squares lower bounds for planted clique”, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC '15) , Nowy Jork, NY, USA: ACM, s. 87-96, arXiv : 1503.06447 , doi : 10.1145/2746539.2746600 , ISBN 978-1-4503-3536-2, S2CID 2754095.
Księżyc, ŚJ; Moser, L. (1965), "Na klikach na wykresach", Izrael Journal of Mathematics , 3 : 23-28, doi : 10.1007/BF02760024 , MR 0182577 , S2CID 9855414.
Nešetřil, J. ; Poljak, S. (1985), „O złożoności problemu podgrafu”, Commentationes Mathematicae Universitatis Carolinae , 26 (2): 415-419.
Östergård, PRJ (2002), "Szybki algorytm dla maksymalnego problemu kliki", dyskretna matematyka stosowana , 120 (1-3): 197-207, doi : 10,1016/S0166-218X (01) 00290-6.
Ouyang, Q.; Kaplana, PD; Liu, S.; Libchaber, A. (1997), "Rozwiązanie DNA maksymalnego problemu kliki", Science , 278 (5337): 446-449, Bibcode : 1997Sci...278..446O , doi : 10.1126/science.278.5337.446 , PMID 9334300.
Papadimitriou, Christos H .; Yannakakis, Mihalis (1981), „Klika problem dla grafów płaskich”, Information Processing Letters , 13 (4-5): 131-133, doi : 10.1016/0020-0190 (81) 90041-7 , MR 0651460.
Pardalos, PM; Rogers, GP (1992), „Algorytm rozgałęzienia i związany dla maksymalnego problemu kliki”, Computers & Operations Research , 19 (5): 363-375, doi : 10.1016/0305-0548(92)90067-F.
Razborov, AA (1985), „Dolne granice dla złożoności monotonii niektórych funkcji logicznych”, Proceedings of USSR Academy of Sciences (w języku rosyjskim), 281 : 798-801. Tłumaczenie na język angielski w sow. Matematyka. Dokl. 31 (1985): 354-357CS1 maint: postscript ( link ).
Regina, J.-C. (2003), „Używanie programowania z ograniczeniami do rozwiązania problemu maksymalnej kliki”, Proc. 9. Międz. Konf. Zasady i praktyka programowania z ograniczeniami – CP 2003 , Lecture Notes in Computer Science, 2833 , Springer-Verlag , s. 634–648, doi : 10.1007/978-3-540-45193-8_43.
Rodos, Mikołaj; Willetta, Piotra; Cielę, Alain; Dunbar, James B.; Humblet, Christine (2003), „CLIP: similarity search of 3D databases using clique detection”, Journal of Chemical Information and Computer Sciences , 43 (2): 443-448, doi : 10.1021/ci025605o , PMID 12653507.
Robson, JM (1986), "Algorytmy dla maksymalnych niezależnych zbiorów", Journal of Algorithms , 7 (3): 425-440, doi : 10.1016/0196-6774 (86) 90032-5.
Robson, JM (2001), Znajdowanie maksymalnego zbioru niezależnego w czasie $O (2 n /4)$ .
Rosgen, B; Stewart, L (2007), „Złożoność wyników na wykresach z kilkoma klikami” , Matematyka dyskretna i informatyka teoretyczna , 9 (1): 127-136.
Samudrala, Ram; Moult, John (1998), "Algorytm teorii grafów do porównawczego modelowania struktury białka", Journal of Molecular Biology , 279 (1): 287-302, doi : 10.1006/jmbi.1998.1689 , PMID 9636717.
Sethuraman, Samyukta; Butenko, Sergiy (2015), „Problem kliki o maksymalnym współczynniku”, Computational Management Science , 12 (1): 197-218, doi : 10.1007/s10287-013-0197-z , MR 3296231 , S2CID 46153055.
Song, Y. (2015), „O niezależnym problemie zbiorów w wykresach losowych” , International Journal of Computer Mathematics , 92 (11): 2233–2242, doi : 10.1080/00207160.2014.976210 , S2CID 6713201.
Spirin, Wiktor; Mirny, Leonid A. (2003), "Białkowe kompleksy i moduły funkcjonalne w sieciach molekularnych", Proceedings of the National Academy of Sciences , 100 (21): 12123-12128, Bibcode : 2003PNAS..10012123S , doi : 10.1073/pnas. 2032324100 , PMC 218723 , PMID 14517352.
Tarjan, RE ; Trojanowski, AE (1977), „Znalezienie maksymalnego niezależnego zestawu” (PDF) , SIAM Journal on Computing , 6 (3): 537-546, doi : 10.1137/0206038.
Tomita E.; Kameda, T. (2007), „Wydajny algorytm branch-and-bound do znajdowania maksymalnej kliki z eksperymentami obliczeniowymi”, Journal of Global Optimization , 37 (1): 95-111, doi : 10.1007/s10898-006-9039 -7 , S2CID 21436014.
Tomita E.; Seki, T. (2003), „Efektywny algorytm rozgałęzienia i wiązania do znajdowania maksymalnej kliki” , Matematyka dyskretna i informatyka teoretyczna , Notatki z informatyki, 2731 , Springer-Verlag, s. 278-289 , doi : 10.1007/3-540-45066-1_22 , ISBN 978-3-540-40505-4.
Tomita E.; Tanaka, A.; Takahashi, H. (2006), „Najgorszy przypadek złożoności czasowej dla generowania wszystkich maksymalnych klik i eksperymentów obliczeniowych”, Informatyka teoretyczna , 363 (1): 28-42, doi : 10.1016/j.tcs.2006.06.015.
Tsukiyama, S.; Ide, M.; Ariyoshi, I.; Shirakawa, I. (1977), „Nowy algorytm generowania wszystkich maksymalnych niezależnych zbiorów”, SIAM Journal on Computing , 6 (3): 505-517, doi : 10.1137/0206036.
Valiant, LG (1983), „Wykładnicze dolne granice dla ograniczonych obwodów monotonicznych”, Proc. XV Sympozjum ACM z Teorii Informatyki , s. 110-117, doi : 10.1145/800061.808739 , ISBN 0-89791-099-0, S2CID 6326587.
Wasilewska, V. ; Williams, R. (2009), „Znajdowanie, minimalizowanie i liczenie ważonych podgrafów”, Proc. 41. Sympozjum ACM na temat teorii obliczeń , s. 455–464, CiteSeerX 10.1.1.156.345 , doi : 10.1145/1536414.1536477 , ISBN 978-1-60558-506-2, S2CID 224579.
Wegener, I. (1988), „O złożoności programów rozgałęziających i drzew decyzyjnych dla funkcji klikowych ”, Journal of the ACM , 35 (2): 461-472, doi : 10.1145/42282.46161 , S2CID 11967153.
Yuster, R. (2006), „Finding and counting cliques and Independent sets in r- uniform hypergraphs”, Information Processing Letters , 99 (4): 130–134, doi : 10.1016/j.ipl.2006.04.005.
Zuckerman, D. (2006), "Ekstraktory stopni liniowych i nieprzybliżalność maksymalnej kliki i liczby chromatycznej", Proc. 38. ACM Symp. Teoria obliczeń , s. 681-690, doi : 10.1145/1132516.1132612 , ISBN 1-59593-134-1, S2CID 5713815 , ECCC TR05-100.

Languages

In other projects