Problem z kliką

Algorytm brutalnej siły znajduje 4-klikę w tym 7-wierzchołkowym grafie (dopełnienie 7-wierzchołkowego wykresu ścieżki ) poprzez systematyczne sprawdzanie kompletności wszystkich podgrafów C (7,4) = 35 4-wierzchołkowych.

W informatyce problem kliki jest problemem obliczeniowym polegającym na znalezieniu klik (podzbiorów wierzchołków sąsiadujących ze sobą, zwanych także pełnymi podgrafami ) na grafie . 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 kliki maksymalnej (kliki z największą możliwą liczbą wierzchołków), znalezienie kliki o maksymalnej wadze na grafie ważonym, wyliczenie wszystkich klik maksymalnych (kliki, których nie można powiększyć) i rozwiązanie problemu decyzyjnego testowania, czy graf zawiera klikę większą niż zadany rozmiar.

Problem kliki pojawia się w następującej sytuacji w świecie rzeczywistym. Rozważmy sieć społecznościową , w której wierzchołki grafu reprezentują osoby, a krawędzie grafu reprezentują wspólnych znajomych. Wtedy klika reprezentuje podzbiór ludzi, którzy się znają, a algorytmy wyszukiwania klik mogą być użyte do odkrycia tych grup wspólnych znajomych. 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 znalezienia maksymalnej kliki jest zarówno trudny do rozwiązania , jak i trudny do przybliżenia przy ustalonych parametrach . A wypisanie wszystkich maksymalnych klik może wymagać wykładniczego czasu , ponieważ istnieją wykresy z wykładniczo wieloma maksymalnymi klikami. Dlatego większość teorii dotyczącej problemu kliki jest poświęcona identyfikacji specjalnych typów grafów, które dopuszczają bardziej wydajne algorytmy, lub ustaleniu trudności obliczeniowej ogólnego problemu w różnych modelach obliczeń.

Aby znaleźć maksymalną klikę, można systematycznie sprawdzać wszystkie podzbiory, ale ten rodzaj brutalnego wyszukiwania jest zbyt czasochłonny, aby był praktyczny w przypadku sieci zawierających więcej niż kilkadziesiąt wierzchołków. Chociaż żaden algorytm czasu wielomianowego nie jest znany dla tego problemu, znane są bardziej wydajne algorytmy niż wyszukiwanie siłowe. Na przykład algorytm Brona-Kerboscha może być użyty do wylistowania wszystkich maksymalnych klik w czasie optymalnym w najgorszym przypadku, a także możliwe jest wypisanie ich w czasie wielomianowym na klikę.

Historia i zastosowania

Badanie kompletnych podgrafów w matematyce poprzedza terminologię „kliki”. Na przykład kompletne podgrafy pojawiają się wcześnie w literaturze matematycznej w teoretycznym przeformułowaniu teorii Ramseya przez Erdősa i Szekeresa (1935) . Ale termin „klika” i problem algorytmicznego wyszczególniania klik wywodzą się z nauk społecznych, gdzie pełne podwykresy są używane do modelowania klik społecznych , grup ludzi, którzy się znają. Luce i Perry (1949) wykorzystali grafy do modelowania sieci społecznościowych 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 motywacją było zastosowanie socjologiczne. Badacze nauk społecznych zdefiniowali również różne inne typy klik i maksymalnych klik w sieciach społecznościowych, „spójne podgrupy” ludzi lub aktorów w sieci, z których wszyscy mają jeden z kilku różnych rodzajów relacji łączności. Wiele z tych uogólnionych koncepcji klik można również znaleźć, konstruując nieskierowany graf, którego krawędzie reprezentują powiązane pary aktorów z sieci społecznościowej, a następnie stosując algorytm problemu kliki do tego grafu.

Od czasu prac Harary'ego i Rossa wielu innych opracowało algorytmy dla różnych wersji problemu kliki. W latach 70. badacze zaczęli badać te algorytmy z punktu widzenia analizy najgorszego przypadku . Patrz, na przykład, Tarjan i Trojanowski (1977) , wczesna praca na temat najgorszego przypadku złożoności problemu maksymalnej kliki. Również w latach siedemdziesiątych XX wieku, począwszy od prac Cooka (1971) i Karpa (1972) , badacze zaczęli wykorzystywać teorię NP-zupełności i związane z nią wyniki trudności, aby zapewnić matematyczne wyjaśnienie postrzeganej trudności problemu kliki. W latach 90. XX wieku opublikowano przełomową serię artykułów, począwszy od Feige et al. (1991) i opublikowali w The New York Times , wykazali, że (zakładając P ≠ NP ) nie jest nawet możliwe dokładne i wydajne przybliżenie problemu.

Algorytmy wyszukiwania klik były stosowane w chemii do znajdowania substancji chemicznych pasujących do docelowej struktury oraz do modelowania dokowania molekularnego i miejsc wiązania reakcji chemicznych. Można ich również użyć do znalezienia podobnych struktur w różnych cząsteczkach. W tych zastosowaniach tworzy się graf, 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 reprezentowane przez nie dopasowania są ze sobą zgodne. Kompatybilność może na przykład oznaczać, że odległości między atomami w dwóch cząsteczkach są w przybliżeniu równe, z pewną 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 użycie iloczynu modułowego grafów do zredukowania problemu znalezienia maksymalnego wspólnego indukowanego podgrafu dwóch grafów do problemu znalezienia maksymalnej kliki w ich iloczynie.

W automatycznym generowaniu wzorców testowych znalezienie klik może pomóc w określeniu rozmiaru zestawu testów. W bioinformatyce algorytmy wyszukiwania klik zostały wykorzystane do wnioskowania o drzewach ewolucyjnych , przewidywania struktur białek i znajdowania ściśle oddziałujących klastrów białek. Wyliczenie klik na wykresie zależności jest ważnym krokiem w analizie pewnych procesów losowych. W matematyce przypuszczenie Kellera dotyczące układania hipersześcianów twarzą w twarz zostało obalone przez Lagariasa i Shora (1992) , którzy użyli algorytmu wyszukiwania klik na powiązanym wykresie, aby znaleźć kontrprzykład.

Definicje

Główny artykuł: Clique (teoria grafów)

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} .

Graf nieskierowany jest tworzony przez skończony zbiór wierzchołków i zbiór nieuporządkowanych par wierzchołków, które nazywamy krawędziami . Zgodnie z konwencją, w analizie algorytmicznej liczba wierzchołków w grafie jest oznaczana przez n , a liczba krawędzi przez m . Klika w grafie G jest pełnym podgrafem 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 . Klika maksymalna to taka, do której nie można dodać więcej wierzchołków. Dla każdego wierzchołka v , który nie jest częścią maksymalnej kliki, musi istnieć inny wierzchołek w , który należy do kliki i nie sąsiaduje z v , zapobiegając dodaniu v do kliki. Klika maksymalna to taka, która zawiera największą możliwą liczbę wierzchołków. Liczba kliki ω ( G ) to liczba wierzchołków w maksymalnej kliki G .

Zbadano kilka blisko powiązanych problemów związanych ze znajdowaniem klik.

• W problemie maksymalnej kliki wejście jest grafem nieskierowanym, a wyjście jest maksymalną kliką na grafie. Jeśli istnieje wiele maksymalnych klik, jedną z nich można wybrać dowolnie.
• W problemie ważonej maksymalnej kliki dane wejściowe to graf nieskierowany z wagami na jego wierzchołkach (lub rzadziej krawędziach), a dane wyjściowe to 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 dwukryterialnej.
• W problemie listy maksymalnej kliki dane wejściowe są grafem nieskierowanym, a dane wyjściowe są listą wszystkich jego maksymalnych klik. Problem maksymalnej kliki można rozwiązać, stosując jako podprogram algorytm dla problemu listy maksymalnej kliki, ponieważ maksymalna klika musi być zawarta wśród wszystkich maksymalnych klik.
• W problemie k -kliki dane wejściowe to graf nieskierowany i liczba k . Wynikiem jest klika z k wierzchołkami, jeśli taki 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 są grafem nieskierowanym i liczbą k , a danymi wyjściowymi są wartości logiczne : prawda, jeśli wykres zawiera k -klikę, w przeciwnym razie fałsz.

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

Problem kliki i problem zbioru niezależnego są komplementarne: klika w G jest niezależnym zbiorem na wykresie dopełnienia G i odwrotnie. Dlatego wiele wyników obliczeń można równie dobrze zastosować do każdego problemu, 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, gdy są stosowane do ograniczonych rodzin grafów. Na przykład problem kliki można rozwiązać w czasie wielomianowym dla grafów planarnych , podczas gdy problem zbioru niezależnego pozostaje NP-trudny na grafach planarnych.

Algorytmy

Znalezienie pojedynczej maksymalnej kliki

Klika maksymalna , czasami nazywana inkluzją-maksymalną, to klika, która nie jest częścią większej kliki. Dlatego każda klika zawiera się w kliki maksymalnej. Maksymalne kliki mogą być bardzo małe. Graf może zawierać niemaksymalną klikę z wieloma wierzchołkami i oddzielną klikę o rozmiarze 2, która jest maksymalna. Podczas gdy maksymalna (tj. największa) klika jest koniecznie maksymalna, sytuacja odwrotna nie zachodzi. Istnieje kilka typów grafów, w których każda maksymalna klika jest maksymalna; są to dopełnienia dobrze pokrytych grafów , w których każdy maksymalny niezależny zbiór jest maksymalny. 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), rozwijaj bieżącą klikę o jeden wierzchołek naraz, przeglądając pozostałe wierzchołki grafu. Dla każdego wierzchołka v , który bada ta pętla, dodaj v do kliki, jeśli sąsiaduje z każdym wierzchołkiem, który już jest w kliku, i odrzuć v w przeciwnym razie. Algorytm ten działa w czasie liniowym . Ze względu na łatwość znalezienia maksymalnych klik i ich potencjalnie mały rozmiar, więcej uwagi poświęcono znacznie trudniejszemu algorytmicznemu problemowi znalezienia maksymalnej lub w inny sposób dużej kliki. Jednak niektóre badania algorytmów równoległych dotyczyły problemu znalezienia maksymalnej kliki. W szczególności wykazano, że problem znalezienia leksykograficznie pierwszej kliki maksymalnej (tej znalezionej przez powyższy algorytm) jest kompletny dla klasy funkcji czasu wielomianowego . Wynik ten sugeruje, że jest mało prawdopodobne, aby problem był rozwiązywalny w klasie złożoności równoległej NC .

Kliki o stałym rozmiarze

Można sprawdzić, czy graf G zawiera k -wierzchołkową klikę i znaleźć dowolną taką klikę, która zawiera, używając algorytmu brutalnej siły . Algorytm ten bada każdy podgraf z k wierzchołkami i sprawdza, czy tworzy on klikę. Zajmuje to czas   O ( n ^k k ² ) , co wyrażono za pomocą notacji dużego O . Dzieje się tak, ponieważ istnieje O ( n ^k ) podgrafów do sprawdzenia, z których każdy ma O ( k ² ) krawędzi, których obecność w G wymaga sprawdzenia. Zatem 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 zmieniać się jako część danych wejściowych do problemu, czas jest wykładniczy.

Najprostszym nietrywialnym przypadkiem problemu znajdowania klik jest znalezienie trójkąta na wykresie lub równoważne określenie, czy wykres jest pozbawiony trójkątów . W grafie G o m krawędziach może być co najwyżej trójkątów Θ( m ^3/2 ) (używając notacji big theta , aby wskazać, że ta granica jest ścisła). Najgorszy przypadek dla tej formuły ma miejsce, gdy G samo w sobie jest kliką. Dlatego algorytmy wyliczania wszystkich trójkątów muszą zająć co najmniej Ω ( m ^3/2 ) czasu w najgorszym przypadku (przy użyciu notacji dużej omegi ), a znane są algorytmy, które dopasowują się 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 stopnia, a następnie przechodzi 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 lista. Aby to zrobić, algorytm zaznacza wszystkich sąsiadów v , przeszukuje wszystkie krawędzie sąsiada v , wyprowadzają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 dla tego algorytmu jest proporcjonalny do arboryczności grafu (oznaczonej a ( G ) ) pomnożonej przez liczbę krawędzi, która wynosi   O ( m a ( G )) . Ponieważ arboryczność wynosi co najwyżej O ( m ^1/2 ) , algorytm ten działa w czasie O ( m ^3/2 ) . Mówiąc bardziej ogólnie, wszystkie k -wierzchołków można wyświetlić za pomocą podobnego algorytmu, który zajmuje czas proporcjonalny do liczby krawędzi pomnożonej przez arboryczność do potęgi ( k - 2) . W przypadku grafów o stałej arboryczności, takich jak grafy planarne (lub ogólnie grafy z dowolnej nietrywialnej rodziny grafów mniejszych-zamkniętych ), algorytm ten zajmuje czas O ( m ) , co jest optymalne, ponieważ ma liniowy rozmiar danych wejściowych.

Jeśli ktoś pragnie tylko jednego trójkąta lub pewności, że wykres nie zawiera trójkątów, możliwe są szybsze algorytmy. Jak Itai i Rodeh (1978) , graf zawiera trójkąt wtedy i tylko wtedy, gdy jego macierz sąsiedztwa i kwadrat macierzy sąsiedztwa zawierają wpisy niezerowe w tej samej komórce. Dlatego szybkiego mnożenia macierzy można zastosować do znajdowania trójkątów w czasie O ( n ^2,376 ) . Alon ^, O ( m1,41 ) Yuster i Zwick (1994) wykorzystali szybkie mnożenie macierzy, aby ulepszyć algorytm O ( m3 ^/2 ) do wyszukiwania trójkątów do . Algorytmy te oparte na szybkim mnożeniu macierzy zostały również rozszerzone na problemy znajdowania k -klik dla większych wartości k .

Lista wszystkich maksymalnych klik

Zgodnie z wynikami Moona i Mosera (1965) każdy n -wierzchołkowy graf ma co najwyżej 3 ^{n /3} maksymalnych klik. Można je wymienić za pomocą algorytmu Brona-Kerboscha , rekurencyjnej procedury śledzenia wstecznego Brona i Kerboscha (1973) . Główny podprogram rekurencyjny tej procedury ma trzy argumenty: częściowo skonstruowaną (niemaksymalną) klikę, zestaw kandydujących wierzchołków, które można dodać do kliki, oraz inny zestaw wierzchołków, których nie należy dodawać (ponieważ doprowadziłoby to do do kliki, która została już 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 zbioru wierzchołków, których nie należy ponownie dodawać. Można pokazać, że warianty tego algorytmu mają czas działania w najgorszym przypadku O (3 ^{n /3} ) , odpowiadający liczbie klik, które mogą wymagać wyliczenia. Dlatego zapewnia to optymalne rozwiązanie problemu wyliczenia wszystkich maksymalnych klik w najgorszym przypadku. Co więcej, algorytm Brona-Kerboscha był szeroko opisywany jako szybszy w praktyce niż jego alternatywy.

Jednak gdy liczba klik jest znacznie mniejsza niż w najgorszym przypadku, preferowane mogą być inne algorytmy. Jak Tsukiyama i in. (1977) wykazali, że możliwe jest również wypisanie 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, jest znany jako algorytm wrażliwy na dane wyjściowe . Ich algorytm opiera się na następujących dwóch obserwacjach, odnoszących maksymalne kliki danego grafu G do maksymalnych klik 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 samo 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 zostać utworzona z maksymalnej kliki K w G \ v przez dodanie v i usunięcie elementów niebędących sąsiadami z v od K .

Wykorzystując te obserwacje, mogą wygenerować wszystkie maksymalne kliki w G za pomocą algorytmu rekurencyjnego, który wybiera wierzchołek v arbitralnie, 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 macierzystej G \ v , więc eliminują duplikaty, wysyłając klikę w G tylko wtedy, gdy jej rodzic w G \ v jest leksykograficznie maksymalny spośród wszystkich możliwych klik nadrzędnych. 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) poprawiają to do O ( ma ) na klikę, gdzie a jest arborycznością danego grafu. Makino i Uno (2004) zapewniają alternatywny algorytm wrażliwy na dane wyjściowe, oparty na szybkim mnożeniu macierzy. Johnson i Yannakakis (1988) pokazują, że możliwe jest nawet wymienienie wszystkich maksymalnych klik w porządku leksykograficznym z opóźnieniem wielomianowym na klikę. Jednak wybór kolejności jest ważny dla wydajności tego algorytmu: dla odwrotności tej kolejności nie ma algorytmu opóźnienia wielomianowego, 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 wielomianowo. Rodziny te obejmują grafy akordowe , grafy kompletne , grafy bez trójkątów , grafy interwałowe , grafy o ograniczonej pudełkowatości i grafy planarne . W szczególności grafy planarne mają O ( n ) klik o co najwyżej stałym rozmiarze, które można wymienić 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łą razy liczbę wierzchołków), jak i domknięta w wyniku operacji brania podgrafów.

Znajdowanie maksymalnych klik w dowolnych grafach

Możliwe jest znalezienie maksymalnej kliki lub liczby klik dowolnego wykresu n -wierzchołków w czasie O (3 ^{n /3} ) = O (1,4422 ⁿ ) za pomocą jednego z algorytmów opisanych powyżej w celu wyświetlenia listy wszystkich maksymalnych klik w wykres i zwraca największy. 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 ⁿ ) . Jest to rekurencyjny schemat ś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 ⁿ ) , a Robson (1986) poprawił go do czasu O (2 ^{0,276 n} ) = O (1,2108 ⁿ ) , kosztem większego wykorzystania przestrzeni . Algorytm Robsona łączy podobny schemat śledzenia wstecznego (z bardziej skomplikowaną analizą przypadków) i dynamiczną technikę programowania, 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żą do skrócenia rekurencji wstecznej. Najszybszy znany dziś algorytm to udoskonalona wersja tej metody autorstwa Robsona (2001) , która działa w czasie O (2 ^{0,249 n} ) = O (1,1888 ⁿ ) .

Przeprowadzono również szeroko zakrojone badania nad algorytmami heurystycznymi do rozwiązywania problemów z maksymalną kliką bez gwarancji wykonania w najgorszym przypadku, w oparciu o metody obejmujące rozgałęzienie i ograniczenie , wyszukiwanie lokalne , algorytmy zachłanne i programowanie z ograniczeniami . Niestandardowe metodologie obliczeniowe, które zostały zaproponowane do znajdowania klik, obejmują obliczenia DNA i adiabatyczne obliczenia kwantowe . Problem maksymalnej kliki był przedmiotem wyzwania wdrożeniowego sponsorowanego przez DIMACS w latach 1992–1993 oraz zbioru wykresów używanych 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) definiującej permutacji.

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 można wymienić w czasie liniowym. W szczególności w przypadku grafów planarnych, zgodnie z twierdzeniem Kuratowskiego , każda klika może mieć co najwyżej cztery wierzchołki .

Grafy doskonałe są definiowane przez to, że liczba ich 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 grafów doskonałych możliwe jest znalezienie maksymalnej kliki w czasie wielomianowym za pomocą algorytmu opartego na programowaniu półokreślonym . Jednak ta metoda jest złożona i niekombinatoryczna, a dla wielu podklas doskonałych grafów opracowano wyspecjalizowane algorytmy wyszukiwania klik. W grafach dopełnień grafów dwudzielnych twierdzenie Kőniga umożliwia rozwiązanie problemu maksymalnej kliki 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 wykres i można ją znaleźć za pomocą znanych algorytmów dla problemu najdłuższego malejącego podciągu. I odwrotnie, każdy przypadek problemu najdłuższego malejącego podciągu można opisać równoważnie jako problem znalezienia maksymalnej kliki na grafie permutacji. Nawet Pnueli i Lempel (1972) dostarczają alternatywnego algorytmu czasu kwadratowego dla maksymalnych klik w grafach porównywalności , szerszej klasy grafów doskonałych, która obejmuje grafy permutacji jako szczególny przypadek. W grafach akordowych maksymalne kliki można znaleźć, wymieniając wierzchołki w kolejności eliminacji i sprawdzając sąsiedztwa 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 grafem permutacyjnym, więc maksymalną klikę na grafie kołowym można znaleźć, stosując algorytm grafu permutacyjnego do każdego sąsiedztwa. Podobnie w grafie dysku jednostkowego (ze znaną reprezentacją geometryczną) istnieje algorytm czasu wielomianowego dla maksymalnych klik oparty na zastosowaniu algorytmu dopełnień grafów dwudzielnych do wspólnych sąsiedztw par wierzchołków.

Algorytmiczny problem znalezienia maksymalnej kliki na grafie losowym narysowanym 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) został zaproponowany przez Karpa (1976) . Ponieważ maksymalna klika na grafie losowym ma rozmiar logarytmiczny z dużym prawdopodobieństwem, można ją znaleźć metodą brutalnego wyszukiwania w oczekiwanym czasie 2 ^{O (log 2 n )} . Jest to quasi-wielomian związany z czasem . Chociaż liczba klik takich grafów jest zwykle bardzo bliska 2 log ₂ n , proste algorytmy zachłanne , jak również bardziej wyrafinowane techniki aproksymacji losowej znajdują tylko kliki o rozmiarze log ₂ n , czyli o połowę mniejszym. Liczba maksymalnych klik na takich grafach jest z dużym prawdopodobieństwem wykładnicza w log ² n , co uniemożliwia działanie metod, które wymieniają wszystkie maksymalne kliki, w czasie wielomianowym. Ze względu na trudność tego problemu kilku autorów zbadało zasadzonej kliki , problem kliki 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 Ω ( √ n ) , obecnie nie są znane żadne algorytmy czasu wielomianowego, które wykrywałyby te o rozmiarze o ( √ n ) (wyrażone przy użyciu notacji little-o ).

Algorytmy aproksymacyjne

Kilku autorów rozważało algorytmy aproksymacji , które próbują znaleźć klikę lub niezależny zbiór, który, chociaż nie jest maksymalny, ma rozmiar tak bliski maksimum, jaki można znaleźć w czasie wielomianowym. Chociaż większość tych prac koncentrowała się na niezależnych zbiorach w grafach rzadkich, co nie ma sensu w przypadku problemu komplementarnej kliki, pracowano również nad algorytmami aproksymacyjnymi, które nie wykorzystują takich założeń dotyczących rzadkości.

Feige (2004) opisuje wielomianowy algorytm czasu, który znajduje klikę o rozmiarze Ω((log n log log n ) ² ) Ω( n /log ^kn ) / na dowolnym grafie, który ma liczbę klik dla dowolnej stałej k . Używając tego algorytmu, gdy liczba klik danego grafu wejściowego mieści się w przedziale od n /log n do n /log ³ n , przełączając się na inny algorytm Boppany i Halldórssona (1992) dla grafów o wyższych liczbach klik i wybierając dwu- wierzchołków, jeśli oba algorytmy niczego nie znajdą, Feige zapewnia algorytm aproksymacji, który znajduje klikę z liczbą wierzchołków w obrębie współczynnika O( n (log log n ) ² / log ³ 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 ze współczynnikiem 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 kliki. Zielone wierzchołki tworzą 3-klikę i odpowiadają satysfakcjonującemu zadaniu.

Problem decyzyjny kliki jest NP-zupełny . Był to jeden z 21 oryginalnych problemów Richarda Karpa , przedstawionych jako NP-zupełne w jego artykule z 1972 r. „Reducibility Among Combinatorial Problems”. Problem ten został również poruszony w Stephena Cooka wprowadzającym teorię problemów NP-zupełnych. Ze względu na twardość 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 wielkość maksymalnej kliki z parametrem wielkości podanym jako dane wejściowe w problemie decyzyjnym.

Dowód NP-zupełności Karpa jest wielokrotną redukcją problemu spełnialności Boole'a . Opisuje, jak tłumaczyć formuły boolowskie w koniunkcyjnej postaci normalnej (CNF) na równoważne przypadki problemu maksymalnej kliki. Z kolei spełnialność została udowodniona jako NP-zupełna w twierdzeniu Cooka-Levina . Z podanej formuły CNF Karp tworzy graf, który ma wierzchołek dla każdej pary ( v , c ) , gdzie v jest zmienną lub jej zaprzeczeniem, a c 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 istnieje krawędź od ( v , c ) do ( u , d ) zawsze, gdy c ≠ d oraz u i v nie są swoimi negacjami. Jeśli k oznacza liczbę klauzul w formule CNF, to kliki wierzchołków k na tym grafie reprezentują spójne sposoby przypisywania wartości logicznych do niektórych jego zmiennych w celu spełnienia formuły. Dlatego formuła jest spełnialna wtedy i tylko wtedy, gdy k -klika wierzchołków.

Niektóre problemy NP-zupełne (takie jak problem komiwojażera na grafach planarnych ) można rozwiązać w czasie, który jest wykładniczy w funkcji podliniowej parametru wielkości wejściowej n , znacznie szybciej niż wyszukiwanie siłowe. Jednak jest mało prawdopodobne, aby takie podwykładnicze ograniczenie czasowe było możliwe dla problemu kliki na dowolnych wykresach, ponieważ implikował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 w grafie n -wierzchołków dla k = 3 i n = 4 . Każde wejście do obwodu koduje obecność lub brak określonej (czerwonej) krawędzi na wykresie. Obwód wykorzystuje jedną wewnętrzną bramkę i do wykrywania każdej potencjalnej k -kliki.

Trudność obliczeniowa problemu kliki sprawiła, że ​​został on użyty do udowodnienia kilku dolnych granic złożoności obwodów . Istnienie kliki o danej wielkości jest właściwością wykresu monotonicznego , co oznacza, że ​​jeśli klika istnieje na danym grafie, będzie istnieć w każdym supergrafie . Ponieważ ta właściwość jest monotoniczna, musi istnieć obwód monotoniczny, wykorzystujący tylko i bramki i/ lub bramki , aby rozwiązać problem decyzyjny kliki dla danej ustalonej wielkości kliki. Można jednak udowodnić, że rozmiar tych obwodów jest superwielomianową funkcją liczby wierzchołków i wielkości 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 z wykorzystaniem bramek ograniczonego wachlarza musi być co najmniej wielomianem wielkości 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 postaci „Czy czerwona krawędź istnieje?”, Dopasowując optymalną granicę n ( n - 1) / 2.

(Deterministyczna) złożoność drzewa decyzyjnego określania właściwości grafu to liczba pytań 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ść boolowskiego drzewa decyzyjnego dla problemu. Jest n ( n − 1)/2 możliwych pytań, które należy zadać. Dlatego dowolną właściwość grafu można określić 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 w najgorszym przypadku), na które musi odpowiedzieć algorytm losowy lub kwantowy, aby poprawnie określić, czy dany graf ma właściwość .

Ponieważ właściwość zawierania kliki jest monotoniczna, jest objęta hipotezą Aanderaa – Karpa – Rosenberga , która stwierdza, że ​​deterministyczna złożoność drzewa decyzyjnego określania dowolnej nietrywialnej właściwości wykresu monotonicznego wynosi dokładnie n ( n - 1) / 2 . W przypadku dowolnych właściwości grafu monotonicznego przypuszczenie to pozostaje niesprawdzone. Jednak dla deterministycznych drzew decyzyjnych i dla dowolnego k w zakresie 2 ≤ k ≤ n , właściwość zawierająca k -klikę okazała się mieć złożoność drzewa decyzyjnego dokładnie n ( n - 1)/2 przez Bollobása (1976) . Deterministyczne drzewa decyzyjne wymagają również rozmiaru wykładniczego do wykrywania klik lub dużego rozmiaru wielomianowego do wykrywania klik o ograniczonej wielkości.

Hipoteza Aanderaa – Karpa – Rosenberga stwierdza również, że złożoność losowego drzewa decyzyjnego nietrywialnych funkcji monotonicznych wynosi Θ ( n ² ) . Hipoteza ponownie pozostaje niepotwierdzona, ale została rozstrzygnięta ze względu na właściwość zawierania k kliki dla 2 ≤ k ≤ n . Wiadomo, że ta właściwość ma losową złożoność drzewa decyzyjnego Θ( n ² ) . W przypadku kwantowych drzew decyzyjnych najlepiej znaną dolną granicą jest Ω( n ) , ale żaden algorytm dopasowujący nie jest znany dla przypadku k ≥ 3 .

Nieustępliwość przy stałych parametrach

Złożoność sparametryzowana to teoretyczne badanie złożoności problemów, które są naturalnie wyposażone w mały parametr całkowitoliczbowy k i dla których problem staje się trudniejszy wraz ze wzrostem k , na przykład znajdowanie k -kliek na grafach. Mówimy, że problem jest rozwiązywany ze stałymi parametrami, jeśli istnieje algorytm do jego rozwiązania na danych wejściowych o rozmiarze n i funkcji f , takiej, że algorytm działa w czasie f ( k ) n ^{O (1)} . Oznacza to, że jest wykonalny ze stałymi parametrami, jeśli można go rozwiązać w czasie wielomianowym dla dowolnej ustalonej wartości k , a ponadto jeśli wykładnik wielomianu nie zależy od k .

Aby znaleźć kliki k -wierzchołków, algorytm wyszukiwania siłowego ma czas działania O( n ^k k ² ) . Ponieważ wykładnik n zależy od k , ten algorytm nie jest wykonalny ze stałymi parametrami. Chociaż można to poprawić przez szybkie mnożenie macierzy, czas działania nadal ma wykładnik, który jest liniowy w k Tak więc, chociaż czas działania znanych algorytmów dla problemu kliki jest wielomianem dla dowolnego ustalonego k , algorytmy te nie wystarczają dla ustalonego parametru ustępliwość. Downey i Fellows (1995) zdefiniowali hierarchię sparametryzowanych problemów, hierarchię W, która, jak przypuszczali, nie ma możliwych do zastosowania algorytmów o stałych parametrach. 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 algorytmu o stałych parametrach, który można zastosować. Co więcej, wynik ten stanowi podstawę dowodów twardości W [1] wielu innych problemów, a tym samym służy jako analogia twierdzenia Cooka -Levina dla złożoności parametrycznej.

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

Chociaż jest mało prawdopodobne, aby problemy z wyszczególnieniem maksymalnych klik lub znalezieniem maksymalnych klik były wykonalne z parametrem k , mogą być rozwiązane z parametrami stałymi dla innych parametrów o złożoności instancji. Na przykład wiadomo, że obydwa problemy są możliwe do rozwiązania ze stałymi parametrami, gdy są sparametryzowane przez degenerację wykresu wejściowego.

Twardość przybliżenia

Wykres relacji zgodności między 2-bitowymi próbkami 3-bitowych ciągów próbnych. Każda maksymalna klika (trójkąt) na tym wykresie reprezentuje wszystkie sposoby próbkowania pojedynczego ciągu 3-bitowego. Dowód nieaproksymowalności problemu kliki obejmuje 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, znane są od dawna. Garey i Johnson (1978) zauważyli, że ponieważ liczba kliki przyjmuje małe wartości całkowite i jest NP-trudna do obliczenia, nie może mieć w pełni 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ładny numer kliki. Jednak niewiele więcej było wiadomo aż do wczesnych lat 90., kiedy kilku autorów zaczęło dostrzegać powiązania między przybliżeniem maksymalnych klik a probabilistycznie sprawdzalnymi dowodami . Wykorzystali te połączenia do udowodnienia twardości wyników aproksymacji dla problemu maksymalnej kliki. Po wielu ulepszeniach tych wyników obecnie wiadomo, że dla każdej liczby rzeczywistej ε > 0 nie może istnieć algorytm czasu wielomianowego, który przybliżałby maksymalną klikę do współczynnika lepszego niż O ( n ^{1 - ε} ) , chyba że P = NP .

Z grubsza idea tych wyników nieprzybliżenia polega na utworzeniu wykresu, który przedstawia 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 sekwencja bitów. Instancja problemu spełnialności powinna mieć ważny dowód wtedy i tylko wtedy, gdy jest spełnialna. Dowód jest sprawdzany przez algorytm, który po obliczeniu danych wejściowych do problemu spełnialności w czasie wielomianowym wybiera zbadanie niewielkiej liczby losowo wybranych pozycji łańcucha dowodowego. W zależności od tego, jakie wartości zostaną znalezione w tej próbce bitów, sprawdzający albo zaakceptuje, albo odrzuci dowód, bez patrzenia na pozostałe bity. Fałszywe negatywy nie są dozwolone: ​​ważny dowód musi być zawsze akceptowany. Jednak nieważny dowód może czasami zostać błędnie zaakceptowany. Dla każdego nieważnego dowodu prawdopodobieństwo, że sprawdzający go zaakceptuje, musi być niskie.

Aby przekształcić probabilistycznie sprawdzalny system dowodowy tego typu w problem kliki, tworzy się graf z wierzchołkiem dla każdego możliwego akceptującego przebiegu sprawdzania 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 zaakceptowanie dowodu przez sprawdzającego. Może być reprezentowany przez częściowe słowo z 0 lub 1 na każdej badanej pozycji i symbolem wieloznacznym na każdej pozostałej pozycji. Na tym grafie dwa wierzchołki sąsiadują ze sobą, jeśli odpowiednie dwa przebiegi akceptujące widzą te same wartości bitów na każdej pozycji, którą oba 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, i wszystkie maksymalne kliki powstają w ten sposób. Jedna z tych klik jest duża wtedy i tylko wtedy, gdy odpowiada ciągowi dowodowemu akceptowanemu przez wielu sprawdzających. Jeśli pierwotna instancja spełnialności jest spełnialna, będzie miała ważny ciąg dowodowy, taki, który jest akceptowany przez wszystkie przebiegi sprawdzania, a ten ciąg będzie odpowiadał dużej kliki na wykresie. Jeśli jednak pierwotna instancja nie jest zadowalająca, wszystkie ciągi dowodowe są nieważne, każdy ciąg dowodowy ma tylko niewielką liczbę przebiegów sprawdzania, które błędnie go akceptują, a wszystkie kliki są małe. Dlatego też, gdyby można było rozróżnić w czasie wielomianowym grafy, które mają duże kliki, i grafy, w których wszystkie kliki są małe, lub gdyby można było dokładnie przybliżyć problem kliki, wówczas zastosowanie tego przybliżenia do grafów wygenerowanych z przypadków spełnialności pozwoliłoby spełnialnym przypadkom odróżnić od niezadowalających przypadków. Jednak nie jest to możliwe, chyba że P = NP.

Notatki

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 klik”, Teoria grafów i obliczenia macierzy rzadkich , IMA Cz. Matematyka Zał., tom. 56, Springer, Nowy Jork, s. 1–29, doi : 10.1007/978-1-4613-8369-7_1 , MR 1320296 .
•   Bomze, IM; Budinich, M.; Pardalos PM; Pelillo, M. (1999), „Maksymalny problem kliki”, Handbook of Combinatorial Optimization , tom. 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 (wyd. 2), MIT Press i McGraw-Hill, s. 1003–1006, ISBN 0-262-03293-7 .
•   Downey, RG; Fellows, MR (1999), Złożoność parametryczna , Springer-Verlag , ISBN 0-387-94883-X .
•   Golumbic, MC (1980), Algorithmic Graph Theory and Perfect Graphs , Informatyka i matematyka stosowana , Academic Press , ISBN 0-444-51530-5 .
•   Grötschel, M .; Lovász, L. ; Schrijver, A. (1988), „9.4 Kolorowanie doskonałych wykresów”, algorytmy geometryczne i optymalizacja kombinatoryczna , algorytmy i kombinatoryka, tom. 2, Springer-Verlag , s. 296–298, ISBN 0-387-13624-X .
•   Gutin, G. (2004), „5.3 Niezależne zestawy 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 .
•   Muegge, Ingo; Rzadko, Matthias (2001), „Dokowanie i punktacja małych cząsteczek”, Recenzje w chemii obliczeniowej , 17 : 1–60, doi : 10.1002/0471224413.ch1 , ISBN 9780471398455 .
•   National Research Council Committee 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), „Heurystyka dla maksymalnej kliki i zestawu niezależnego”, Encyklopedia optymalizacji , Springer, s. 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 , zarchiwizowane z oryginału w dniu 27 maja, 2012 .
•   Sipser, M. (1996), Wprowadzenie do teorii obliczeń , International Thompson Publishing , ISBN 0-534-94728-X .
•   Skiena, Steven S. (2009), Podręcznik projektowania algorytmów (wyd. 2), Springer, ISBN 978-1-84800-070-4 .
•   Valiente, Gabriel (2002), „Rozdział 6: Clique, Independent Set i Vertex Cover”, Algorytmy na drzewach i wykresach , Springer, s. 299–350, doi : 10.1007/978-3-662-04921-1_6 , S2CID 118777692 .
•   Wasserman, Stanley ; Faust, Katherine (1994), Analiza sieci społecznych: metody i zastosowania , Analiza strukturalna w naukach społecznych, tom. 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 badawcze

•   Abello, J.; Pardalos PM; Resende, MGC (1999), „O problemach z maksymalną kliką na bardzo dużych wykresach” (PDF) , w Abello, J .; Vitter, J. (red.), Algorytmy pamięci zewnętrznej , seria DIMACS dotycząca matematyki dyskretnej i informatyki teoretycznej, tom. 50, Amerykańskie Towarzystwo Matematyczne , s. 119–130, ISBN 0-8218-1184-3 .
•   Alon, N .; Boppana, R. (1987), „Monotoniczna złożoność obwodu funkcji boolowskich” , Combinatorica , 7 (1): 1–22, doi : 10.1007 / BF02579196 , S2CID 17397273 .
• Alon, N .; Krivelevich, M.; Sudakov, B. (1998), „Znajdowanie dużej ukrytej kliki na losowym wykresie”, Random Structures & Algorithms , 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 cykli o podanej długości”, Proceedings of the 2nd European Symposium on Algorithms, Utrecht, Holandia , s. 354–364 .
•   Amano, Kazuyuki; Maruoka, Akira (2005), „Dolna granica superwielomianu dla obwodu obliczającego funkcję kliki 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 przybliżenia”, Journal of the ACM , 45 (3): 501–555, doi : 10.1145/278298.278306 , S2CID 8561542 , ECCC TR98-008 . Pierwotnie zaprezentowany na Sympozjum na temat podstaw informatyki w 1992 r. , doi : 10.1109/SFCS.1992.267823 .
•   Arora, S. ; Safra, S. (1998), „Probabilistyczne sprawdzanie dowodów: nowa charakterystyka NP”, Journal of the ACM , 45 (1): 70–122, doi : 10.1145/273865.273901 , S2CID 751563 . Pierwotnie zaprezentowany na Sympozjum na temat podstaw informatyki w 1992 r. , doi : 10.1109/SFCS.1992.267824 .
• Balas, E.; Yu, CS (1986), „Znajdowanie maksymalnej kliki na 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”, Information Processing Letters , 4 (4): 83–84, doi : 10.1016/0020-0190 (76) 90049-1 .
•   Battiti R.; Protasi, M. (2001), „Reaktywne lokalne wyszukiwanie problemu maksymalnej kliki”, Algorithmica , 29 (4): 610–637, doi : 10.1007 / s004530010074 , S2CID 1800512 .
•   Bollobás, Béla (1976), „Kompletne podgrafy są nieuchwytne”, Journal of Combinatorial Theory , Seria B, 21 (1): 1–7, doi : 10.1016/0095-8956 (76) 90021-6 , ISSN 0095-8956 .
•   Boppana, R.; Halldórsson, MM (1992), „Przybliżanie 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: znajdowanie wszystkich klik nieskierowanego wykresu”, Communications of the ACM , 16 (9): 575–577, doi : 10.1145/362342.362367 , S2CID 13886709 .
• Carraghan, R.; Pardalos, PM (1990), „Dokładny algorytm dla problemu maksymalnej kliki”, Operations Research Letters , 9 (6): 375–382, doi : 10.1016/0167-6377 (90) 90057-C .
• Cazals, F.; Karande, C. (2008), „Uwaga na temat problemu zgłaszania maksymalnych klik”, Teoretyczna Informatyka , 407 (1): 564–568, doi : 10.1016/j.tcs.2008.05.010 .
• Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), „Silne dolne granice obliczeniowe poprzez parametryzowaną złożoność”, Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
• Chiba, N.; Nishizeki, T. (1985), „Algorytmy arboryczności i podgrafów”, SIAM Journal on Computing , 14 (1): 210–223, doi : 10.1137/0214017 .
•   Childs, rano; Farhi, E.; Goldstone, J .; Gutmann, S. (2002), „Znajdowanie klik przez kwantową ewolucję adiabatyczną”, Quantum Information and Computation , 2 (3): 181–191, arXiv : quant-ph/0012104 , Bibcode : 2000quant.ph.12104C , doi : 10,26421 /QIC2.3 , S2CID 33643794 .
•   Childs, rano; Eisenberg, JM (2005), „Algorytmy kwantowe do znajdowania podzbiorów”, Quantum Information and Computation , 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 dysków jednostkowych”, Discrete Mathematics , 86 (1–3): 165–177, doi : 10.1016/0012-365X (90) 90358-O
•   Cook, SA (1971), „Złożoność procedur dowodzenia twierdzeń” , Proc. Trzecie sympozjum ACM na temat 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”, Information and Control , 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 o filogenezach na podstawie zgodności”, Systematic Zoology , 35 (2): 224–229, doi : 10.2307/2413432 , JSTOR 2413432 .
• Downey, RG; Stypendyści, MR (1995), „Ustalalność parametrów i kompletność. II. O kompletności dla W [1]”, Teoretyczna informatyka , 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 ustalonych parametrach i zbiorze dominującym”, Theoretical Computer Science , 326 (1–3): 57–67, doi : 10.1016/j.tcs.2004.05.009 .
•   Eppstein, David ; Löffler, Maarten; Strash, Darren (2013), „Lista wszystkich maksymalnych klik na dużych rzadkich wykresach świata rzeczywistego w czasie zbliżonym do optymalnego”, Journal of Experimental Algorithmics , 18 (3): 3,1, arXiv : 1103,0318 , doi : 10,1145/2543629 , S2CID 47515491 .
• Erdős, Paweł ; Szekeres, George (1935), „Problem kombinatoryczny w geometrii” (PDF) , Compositio Mathematica , 2 : 463–470 .
•   Nawet S .; Pnueli, A .; Lempel, A. (1972), „Wykresy permutacyjne i wykresy przechodnie”, Journal of the ACM , 19 (3): 400–410, doi : 10.1145/321707.321710 , S2CID 9501737 .
•   Fahle, T. (2002), „Prosto i szybko: poprawa algorytmu rozgałęzień i ograniczeń dla maksymalnej kliki”, Proc. 10. Europejskie Sympozjum Algorytmów , Notatki z wykładów z informatyki, tom. 2461, Springer-Verlag, s. 47–86, doi : 10.1007/3-540-45749-6_44 , ISBN 978-3-540-44180-9 .
• Feige, U. (2004), „Zbliżanie maksymalnej kliki przez usuwanie 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), „Przybliżona klika jest prawie NP-kompletna”, Proc. 32. Symp. 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), „Znajdowanie i certyfikowanie dużej ukrytej kliki na półlosowym wykresie”, Random Structures and Algorithms , 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), „ Strong” wyniki NP-zupełności: motywacja, przykłady i implikacje”, Journal of the ACM , 25 (3): 499–508, doi : 10.1145/322077.322090 , S2CID 18371269 .
•   Garey, MR ; Johnson, DS ; Stockmeyer, L. (1976), „Niektóre uproszczone problemy z grafami NP-zupełnymi”, Theoretical Computer Science , 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”, Networks , 3 (3): 261–273, doi : 10.1002 / net.3230030305 .
•   Goldmann, M.; Håstad, J. (1992), „Prosta dolna granica dla monotonnej kliki za pomocą 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 losowej złożoności właściwości wykresu monotonicznego” (PDF) , Acta Cybernetica , 10 (3): 119–127 , dostęp 2009-10-02
•   Grosso, A.; Locatelli, M.; Della Croce, F. (2004), „Łączenie zamian i wag węzłów w adaptacyjnym, zachłannym 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), „Aproximations of 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 obwodów kombinowanych”, Proc. Międzynarodowa konferencja IEEE/ACM 1998 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”, Sociometry , American Sociological Association, 20 (3): 205–215, doi : 10.2307/2785673 , JSTOR 2785673 , MR 0110590 .
• Håstad, J. (1999), „Klikę trudno przybliżyć w obrębie 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), „Znajdowanie 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”, Random Structures and Algorithms , 3 (4): 347–359, doi : 10.1002 / rsa.3240030402 .
•   Jian, T (1986), „ Algorytm O (2 ^{0,304 n} ) do rozwiązywania problemu maksymalnego zbioru niezależnego”, IEEE Transactions on Computers , IEEE Computer Society, 35 (9): 847–851, doi : 10.1109/TC.1986.1676847 , ISSN 0018-9340 .
•   Johnson, DS ; Sztuczka, mgr , wyd. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, 11–13 października 1993 , Seria DIMACS w matematyce dyskretnej i informatyce teoretycznej, tom. 26, Amerykańskie Towarzystwo Matematyczne , ISBN 0-8218-6609-5 .
• Johnson, DS ; Yannakakis, M. (1988), „O generowaniu wszystkich maksymalnych niezależnych zestawów”, Information Processing Letters , 27 (3): 119–123, doi : 10.1016/0020-0190 (88) 90065-8 .
• Karp, Richard M. (1972), „redukowalność 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) w dniu 29.06.2011 , 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 maksymalnego problemu kliki”, Information Processing Letters , 95 (5): 503–511, doi : 10.1016/j.ipl.2005.05.010 .
•    Khot, S. (2001), „Ulepszone wyniki nieprzybliżenia dla MaxClique, liczby chromatycznej i przybliżonego kolorowania wykresów”, Proc. 42. Symp. 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), „Wydajne znajdowanie i liczenie małych indukowanych podgrafów”, 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 ograniczeń dla problemu maksymalnej kliki” (PDF) , MATCH Communications in Mathematical and in 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 układania kostek 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), „W kierunku maksymalnych niezależnych zbiorów na masywnych grafach”, Proceedings of the 41. International Conference on Very Large Data Bases (VLDB 2015) (PDF) , Proceedings of the VLDB Endowment, tom. 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), „Dachówka kostki wymiaru ósmego bez współdzielenia twarzy”, Discrete and Computational Geometry , 28 (2): 275–279, doi : 10.1007 / s00454-002-2801-9 , MR 1920144 .
•   Magniez, Fryderyk; Santha, 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” , Teoria algorytmów: SWAT 2004 (PDF) , Notatki z wykładów z informatyki, tom. 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), „Dolne granice sumy kwadratów dla zasadzonej kliki”, 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, JW; Moser, L. (1965), „O klikach na wykresach”, Israel 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 problemu maksymalnej kliki”, Discrete Applied Mathematics , 120 (1–3): 197–207, doi : 10.1016 / S0166-218X (01) 00290-6 .
•   Ouyang, Q.; Kaplan, PD; Liu S.; Libchaber, A. (1997), „DNA rozwiązanie problemu maksymalnej 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), „Problem kliki dla grafów planarnych”, 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 ograniczeń dla problemu maksymalnej kliki”, Computers & Operations Research , 19 (5): 363–375, doi : 10.1016/0305-0548 (92) 90067-F .
• Razborov, AA (1985), „Dolne granice monotonicznej złożoności niektórych funkcji boolowskich”, Proceedings of the USSR Academy of Sciences (w języku rosyjskim), 281 : 798–801. Tłumaczenie angielskie w sow. Matematyka Dokł. 31 (1985): 354–357 {{ cytat }} : CS1 maint: postscriptum ( link ) .
• Régin, J.-C. (2003), „Używanie programowania z ograniczeniami do rozwiązania problemu maksymalnej kliki”, Proc. 9. Int. konf. Zasady i praktyka programowania z ograniczeniami – CP 2003 , Notatki z wykładów z informatyki, tom. 2833, Springer-Verlag , s. 634–648, doi : 10.1007/978-3-540-45193-8_43 .
•   Rodos, Mikołaj; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), „CLIP: wyszukiwanie podobieństw w bazach danych 3D przy użyciu wykrywania klik”, Journal of Chemical Information and Computer Sciences , 43 (2): 443–448, doi : 10.1021/ci025605o , PMID 12653507 .
• Robson, JM (1986), „Algorytmy dla maksymalnych zbiorów niezależnych”, Journal of Algorithms , 7 (3): 425–440, doi : 10.1016/0196-6774 (86) 90032-5 .
• Robson, JM (2001), Znalezienie maksymalnego zbioru niezależnego w czasie O (2 ^{n /4} ) .
• Rosgen, B.; Stewart, L (2007), „Wyniki złożoności 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łek”, Journal of Molecular Biology , 279 (1): 287–302, doi : 10.1006/jmbi.1998.1689 , PMID 9636717 .
•    Sethuraman, Samyukta; Butenko, Sergiy (2015), „Problem kliki maksymalnego współczynnika”, Computational Management Science , 12 (1): 197–218, doi : 10.1007 / s10287-013-0197-z , MR 3296231 , S2CID 46153055 .
•   Song, Y. (2015), „O problemie zbioru niezależnego w grafach losowych” , International Journal of Computer Mathematics , 92 (11): 2233–2242, doi : 10.1080/00207160.2014.976210 , S2CID 6713201 .
•    Spirin, Wiktor; Mirny, Leonid A. (2003), „Kompleksy białkowe 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), „Znajdowanie maksymalnego niezależnego zestawu” (PDF) , SIAM Journal on Computing , 6 (3): 537–546, doi : 10.1137/0206038 .
•   Tomita, E.; Kameda, T. (2007), „Wydajny algorytm rozgałęzień i ograniczeń do znajdowania maksymalnej kliki za pomocą eksperymentów obliczeniowych”, Journal of Global Optimization , 37 (1): 95–111, doi : 10.1007 / s10898-006-9039 -7 , S2CID 21436014 .
•    Tomita, E.; Seki, T. (2003), „Wydajny algorytm rozgałęzień i ograniczeń do znajdowania maksymalnej kliki” , Matematyka dyskretna i informatyka teoretyczna , Notatki z wykładów z informatyki, tom. 2731, Springer-Verlag, s. 278–289 , doi : 10.1007/3-540-45066-1_22 , ISBN 978-3-540-40505-4 , S2CID 21436014 .
• Tomita, E.; Tanaka, A.; Takahashi, H. (2006), „Najgorszy przypadek złożoności czasowej do generowania wszystkich maksymalnych klik i eksperymentów obliczeniowych”, Theoretical Computer Science , 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. 15 Sympozjum ACM na temat teorii informatyki , s. 110–117, doi : 10.1145/800061.808739 , ISBN 0-89791-099-0 , S2CID 6326587 .
•     Vassilevska, V. ; Williams, R. (2009), „Znajdowanie, minimalizowanie i liczenie podgrafów ważonych”, Proc. 41 Sympozjum ACM na temat teorii informatyki , 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 rozgałęzionych programów i drzew decyzyjnych dla funkcji kliki”, Journal of the ACM , 35 (2): 461–472, doi : 10.1145/42282.46161 , S2CID 11967153 .
• Yuster, R. (2006), „Znajdowanie i liczenie klik i niezależnych zbiorów w r -jednolitych hipergrafach”, Information Processing Letters , 99 (4): 130–134, doi : 10.1016/j.ipl.2006.04.005 .
•     Zuckerman, D. (2006), „Ekstraktory stopni liniowych i nieprzybliżenie maksymalnej kliki i liczby chromatycznej”, Proc. 38. ACM Symp. Teoria informatyki , s. 681–690, doi : 10.1145/1132516.1132612 , ISBN 1-59593-134-1 , S2CID 5713815 , ECCC TR05-100 .