Problema clicii

În informatică, problema clicii este problema computațională a găsirii de clici (submulțimi de noduri, toate adiacente reciproc, numite și subgrafuri complete) într-un graf. Ea are mai multe formulări diferite, în funcție de care clici, și care informații despre acestea trebuie să fie găsite. Formulări comune ale problemei clicii sunt găsirea unei clici maxime (o clică cu cel mai mare număr posibil de noduri), găsirea unei clici cu pondere maximă într-un graf ponderat, listarea tuturor clicilor maxime (clici care nu pot fi extinse), și rezolvarea problemei deciziei pe testul dacă un graf conține o clică mai mare decât o anumită dimensiune.

Un algoritm cu forță brută găsește o 4-clică în acest graf cu 7 noduri (complementul grafului liniar de 7 noduri) verificând sistematic completitudinea tuturor C(7,4) = 35 subgrafuri de 4 noduri.

Problema clicii apare în următorul context din lumea reală. Se consideră o rețea socială, în care nodurile grafului reprezintă oamenii, iar muchiile grafului reprezintă cunoașterea reciprocă. Atunci, o clică reprezintă o submulțime de oameni care se cunosc unul pe celălalt, și algoritmii pentru găsirea clicilor pot fi utilizați pentru a descoperi aceste grupuri de prieteni comuni. Împreună cu aplicațiile sale în rețelele sociale, problema clicii are mai multe aplicații și în bioinformatică și chimie computațională.

Cele mai multe versiuni ale problemei clicii sunt grele. Problema deciziei la clici este NP-completă (una dintre cele 21 probleme NP-complete ale lui Karp). Problema găsirii clicii maxime este atât intractabilă parametric^⁠(d) cât și greu de aproximat^⁠(d). Și listarea tuturor clicilor maxime poate necesita timp exponențial întrucât există grafuri cu un număr exponențial de clici maximale. Prin urmare, o mare parte din teoria despre problema clicii este dedicată identificării tipurilor speciale de grafuri care admit mai mulți algoritmi eficienți, sau la stabilirea dificultății computaționale a problemei generale în diferite modele de calcul.

Pentru a găsi o clică maximă, se pot inspecta sistematic toate submulțimile, dar această căutare cu forța brută este prea consumatoare de timp pentru a fi practică în rețele care cuprind mai mult de câteva zeci de noduri. Deși nu se cunoaște niciun algoritm în timp polinomial pentru această problemă, se cunosc unii algoritmi mai eficienți decât căutarea cu forța brută. De exemplu, algoritmul Bron–Kerbosch poate fi folosit pentru a lista toate clicile maxime în timp optim, și este posibilă și listarea lor în timp polinomial pe clică.

Istorie și aplicații

Studiul subgrafurilor complete în matematică precede terminologia de „clică”. De exemplu, subgrafurile complete au apărut pentru prima oară în literatura matematică în reformularea teoriei lui Ramsey în termeni de teoria grafurilor în Erdős & Szekeres (1935). Dar termenul de „clică” și problema listării algoritmice a clicilor provin amândouă din științele sociale, acolo unde subgrafurile completate sunt utilizate pentru a modela clicile sociale^⁠(d), grupuri de oameni care se cunosc unul pe altul. Luce & Perry (1949) au utilizat grafurile pentru a modela rețelele sociale, și a adaptat terminologia științelor sociale pentru teoria grafurilor. Ei au fost primii care au denumit subgrafurile complete „clici”. Primul algoritm pentru rezolvarea problemelor clicii provine de la Harary & Ross (1957), care au fost motivați de aplicabilitatea sociologică. Cercetătorii din științele sociale au definit, de asemenea, diverse alte tipuri de clici și clici maxime în rețelele sociale, „subgrupuri de coeziune” formate din persoane sau actori din rețea care împărtășesc unul dintre mai multe tipuri diferite de legături. Multe dintre aceste generalizări ale clicilor pot fi găsite construind un graf neorientat ale cărui margini reprezintă perechi legate de actori din rețeaua socială, și apoi aplicând un algoritm pentru problema clicii pe acest graf.

După lucrările lui Harary și Ross, mulți alții au conceput algoritmi pentru diverse versiuni ale problemei clicii. În anii 1970, cercetătorii au început să studieze acești algoritmi din punct de vedere al analizei cazului cel mai rău^⁠(d). A se vedea, de exemplu, Tarjan & Trojanowski (1977), o lucrare timpurie privind complexitatea în cel mai rău caz a problemei clicii maxime. De asemenea, în 1970, începând cu munca lui Cook (1971) si Karp (1972), cercetătorii au început să folosească teoria NP-completitudinii și a rezultatelor asociate de intractabilitate pentru a oferi o explicație matematică a dificultății percepute față a problemei clicii. În 1990, o serie de lucrări importante, începând cu Feige et al. (1991) , despre care s-a scris în New York Times, au arătat că (presupunând că P ≠ NP) nici măcar nu este posibil să se aproximeze^⁠(d) problema cu precizie și eficiență.

Algoritmii de găsire a clicii au fost utilizați în chimie, pentru a găsi substanțe chimice care se potrivesc cu o structură țintă și pentru a modela dockingul molecular^⁠(d) și punctele de legare ale reacțiilor chimice. Aceștia pot fi folosiți și pentru a găsi structuri similare în diferite molecule. În aceste aplicații, se formează un graf în care fiecare nod reprezintă o pereche de atomi, câte unul din fiecare din cele două molecule. Două noduri sunt conectate printr-o muchie dacă potrivirile pe care le reprezintă sunt compatibile una cu cealaltă. Compatibilitatea aceasta poate însemna, de exemplu, că distanțele dintre atomii din două molecule sunt aproximativ egale, cu o anumită toleranță. O clică în acest graf reprezintă o mulțime de perechi de atomi, în care toate perechile sunt compatibile cu celelalte. Un caz special al acestei metode este utilizarea de produsului modular al grafurilor^⁠(d) pentru a reduce problema găsirii cele subgrafului indus comun maximal^⁠(d) a două grafuri la problema de găsirii unei clici maxime în produsul lor.

În generarea automată de șabloane de test^⁠(d), găsirea clicilor poate ajuta la legarea mărimii unui set de teste. În bioinformatică, algoritmii de găsirea clicii au fost utilizați pentru a deduce arborii evolutivi, pentru a prezice structurile proteice^⁠(d), și pentru găsirea grupurilor de proteine care interacționează strâns. Listarea clicilor într-un graf de dependențe^⁠(d) este un pas important în analiza anumitor procese aleatoare. În matematică, conjectura lui Keller^⁠(d) din mozaicarea față-în-față a hipercuburilor a fost infirmată de Lagarias & Shor (1992), care a folosit un algoritm de găsire a clicilor pe un graf asociat pentru a identifica un contraexemplu.

Definiții

Graful prezentat are o clică maximă, triunghiul {1,2,5}, și patru alte clici maximale, perechile {2,3}, {3,4}, {4,5}, și {4,6}.

Un graf neorientat este format dintr-o mulțime finită de noduri și o mulțime de perechi neordonate^⁠(d) de noduri, numite muchii. Prin convenție, în analiza algoritmilor, numărul de noduri al unui graf se notează cu n , iar numărul de muchii se notează cu m. O clică în graful G este un subgraf complet al lui G. Adică, este o submulțime K de noduri astfel încât fiecare două noduri din K sunt cele două capete ale unei muchii din G. O clică maximală este o clică la care nu se mai pot adăuga noduri. Pentru fiecare nod v , care nu face parte dintr-o clică maximală, trebuie să existe un alt nod w , care este în clică și nu este adiacent lui v, ceea ce împiedică adăugarea lui v la clică. O clică maximă este o clică ce include cel mai mare număr posibil de noduri. Numărul de clică ω(G) este numărul de noduri dintr-o clică maximă din graful G.

S-au studiat mai multe probleme strâns legate de conceptul de clică.

• În problema clicii maxime, intrarea este un graf neorientat, iar rezultatul este o clică maximă din graf. Dacă există mai multe clici maxime, se poate alege arbitrar una dintre ele.
• În problmea clicii maxime ponderate, la intrare este un graf neorientat cu ponderi pe nodurile sale (sau, mai puțin frecvent, pe muchii) și la ieșire se așteaptă o clică cu ponderea totală maximă. Problema clicii maxime este cazul special în care toate ponderile sunt egale. Ca și problema de optimizării sumei ponderilor, au mai fost studiate și alte probleme de optimizare.
• În problema listării clicilor maximale, la intrare este un graf neorientat, iar rezultatul este o listă a tuturor clicilor maximale. Problema clicii maxime poate fi rezolvată folosind ca subrutină un algoritm pentru listarea clicilor maximale, deoarece clica maximă trebuie să fie inclusă între clicile maximale.
• În problema k-clicii, la intrare este un graf neorientat și un număr k. Rezultatul este o clică cu k noduri, dacă există una, sau, în caz contrar, o valoare specială care indică faptul că nu există nici o k-clică. În unele variante ale acestei probleme, rezultatul ar trebui să listeze toate clicile de dimensiune k.
• În problema deciziei clicii, la intrare este un graf neorientat și un număr k, iar rezultatul este o valoare logică: „adevărat” dacă graful conține o k-clică, și „fals” în caz contrar.

Primele patru dintre aceste probleme sunt importante în aplicații practice. Problema deciziei clicii nu are importanță practică; este formulată în acest mod doar pentru a aplica teoria NP-completitudinii în problema găsirii clicii.

Problema clicii și problema mulțimii independente^⁠(d) sunt complementare: o clică în G este o mulțime independentă în graful complementar^⁠(d) al lui G și vice-versa. Prin urmare, multe rezultate computaționale pot fi aplicate la fel de bine oricărei probleme, și unele lucrări de cercetare nu fac distincție clară între cele două probleme. Cu toate acestea, cele două probleme au proprietăți diferite atunci când se aplică la familii limitate de grafuri. De exemplu, problema clicii poate fi rezolvată în timp polinomial pentru grafuri planare în timp ce problema mulțimii independente este NP-dură pe grafuri planare.

Algoritmi

Găsirea unei singure clici maximale

O clică maximală este o clică ce nu este inclusă într-o clică mai mare. Prin urmare, toate clicile sunt incluse într-o clică maximală. Clicile maximale pot fi foarte mici. Un graf poate conține o clică nemaximală cu multe noduri și o clică separată de dimensiune 2, care este maximală. O clică maximă (adică cea mai mare) este neapărat și maximală, dar reciproca nu este valabilă. Există unele tipuri de grafuri în care toate clicile maximale sunt și maxime; acestea sunt complementarele^⁠(d) unor grafuri bine acoperite^⁠(d), în care toate mulțimile independente maximale sunt maxime. Cu toate acestea, alte grafuri au clici maximale care nu sunt maxime.

O singură clică maximală poate fi găsită printr-un algoritm greedy simplu. Începând cu o clică trivială (de exemplu, orice nod individual, sau chiar mulțimea vidă), și se iterează, la fiecare pas adăugându-se la clică câte un nod din nodurile neincluse ale grafului. Pentru fiecare nod v, la fiecare iterație se verifică dacă este adiacent cu toate nodurile din clică și dacă nu este, este eliminat dintre cele potențiale. Acest algoritm rulează în timp liniar. Din cauza ușurinței de a găsi clici maximale, și datorită dimensiunilor lor potențial mici, se acordă mai multă atenție problemei algoritmice mult mai dificile de a găsi o clică maximă sau, oricum, mare, decât se acordă problemei de a găsi o singură clică maximală. Cu toate acestea, unele cercetări în domeniul algoritmilor paraleli au studiat problema găsirii unei clici maxime. În special, problema de a găsi prima clică maximală în ordine lexicografică^⁠(d) (cea găsită de către algoritmul de mai sus) a fost demonstrată a fi completă^⁠(d) pentru clasa funcțiilor în timp polinomial. Acest rezultat sugerează că problema este puțin probabil să fie rezolvată în clasa de complexitate paralelă NC^⁠(d).

Clici de dimensiune fixă

Se poate testa dacă un graf G conține o clică de k noduri, putându-se găsi astfel orice clică pe care ea o conține, folosind un algoritm cu forță brută^⁠(d). Acest algoritm analizează fiecare subgraf cu k noduri și verifică dacă formează o clică. Este nevoie de timp O(n^k k²), exprimat în notația big O. Aceasta pentru că există O(n^k) subgrafuri de verificat, fiecare având O(k²) muchii a căror prezență în G trebuie să fie verificată. Astfel, problema poate fi rezolvată în timp polinomial ori de câte ori k este constant. Cu toate acestea, atunci când k nu are o valoare fixă, ci poate varia ca parte a datelor de intrare a problemei, timpul este exponențial.

Cel mai simplu caz netrivial de problemă a găsirii clicii este de a găsi un triunghi într-un graf, sau, echivalent, de a determina dacă graful nu are triunghiuri^⁠(d). Într-un graf cu m muchii, pot exista cel mult Θ(m^3/2) triunghiuri (folosind notația big theta pentru a indica faptul că această limită este strictă). Cel mai rău caz pentru această formulă apare atunci când G este el însuși o clică (este graf complet). Prin urmare, algoritmii pentru listarea tuturor triunghiurilor durează cel puțin Ω(m^3/2) în cel mai rău caz (folosind notația big omega), și se cunosc algoritmi care respectă această limitare de timp. De exemplu, Chiba & Nishizeki (1985) descrie un algoritm care sortează nodurile în ordinea gradului, de la cel mai mare la cel mai mic și apoi iterează prin fiecare nod v din lista sortată, în căutarea unor triunghiuri care includ v și care nu includ niciun nod anterior din listă. Pentru a face astfel, algoritmul marchează toți vecinii lui v, caută prin toate muchiile incidente la un vecin al lui v, producând la ieșire un triunghi pentru fiecare muchie ce leagă două noduri marcate, și apoi elimină marcajele și șterge v din graf. După cum arată autorii, timpul pentru acest algoritm este proporțional cu arboricitatea^⁠(d) grafului (notată cu a(G)), înmulțită cu numărul de muchii, adică O(m a(G)). Deoarece arboricitatea este de cel mult O(m^1/2), acest algoritm rulează în timp O(m^3/2). Mai general, toate clicile de k noduri pot fi listate de un algoritm similar care are nevoie de timp proporțional cu numărul de muchii înmulțit cu arboricitatea la puterea (k − 2). Pentru grafuri de arboricitate constantă, cum ar fi grafurile planare (sau, în general, grafurile din orice familie de grafuri minor-închisă^⁠(d) netrivială), acest algoritm durează un timp O(m), care este optim deoarece este liniar în raport cu mărimea intrării.

Dacă se dorește doar un singur triunghi, sau o asigurare că graful este fără triunghiuri, sunt posibili algoritmi și mai rapizi. După cum remarcă Itai & Rodeh (1978), graful conține un triunghi dacă și numai dacă matricea de adiacență și pătratul matricei de adiacență conțin intrări nenule în aceeași celulă. Prin urmare, tehnicile de înmulțire rapidă a matricelor, cum ar fi algoritmul Coppersmith–Winograd poate fi aplicat pentru a găsi triunghiuri în timp O(n^2.376). Alon, Yuster & Zwick (1994) au utilizat înmulțirea rapidă a matricelor pentru a îmbunătăți algoritmul O(m^3/2) pentru găsirea triunghiurilor până la O(m^1.41). Acești algoritmi bazați pe înmulțirile rapide ale matricelor au fost extinse și la problemea găsirii de k-clici pentru valori mai mari ale lui k.

Listarea tuturor clicilor maximale

Conform unui rezultat din Moon & Moser (1965), fiecare graf de n noduriare cel mult 3^n/3 clici maximale. Acestea pot fi enumerate de algoritmul Bron–Kerbosch, o metodă backtracking recursivă propusă în Bron & Kerbosch (1973). Principala subrutină recursivă a acestei proceduri are trei argumente: o clică parțială construită (nemaximală), o mulțime de noduri-candidat care ar putea fi adăugate la clică, și o altă mulțime de noduri, care nu ar trebui să fie adăugată (deoarece adăugarea lor ar conduce la o clică deja găsită). Algoritmul încearcă adăugarea nodurilor-candidat, unul câte unul la clica parțială, făcând un apel recursiv pentru fiecare. După încercarea fiecăruia dintre aceste noduri, ele sunt trecute în mulțimea de noduri care nu ar trebui să fie adăugate. Se poate demonstra că unele variante ale acestui algoritm au timp de rulare în cel mai rău caz O(3^n/3), corespunzător numărului de clici care ar putea să trebuiască enumerate. Prin urmare, aceasta oferă o soluție optimă în cel mai rău caz la problema listării tuturor clicilor maximale. Mai mult, algoritmul Bron–Kerbosch a fost testat în practică, și testele au relevat faptul că este mai rapid decât alternativele sale.

Cu toate acestea, atunci când numărul de clici este semnificativ mai mic decât cel mai rău caz, sunt preferabili alți algoritmi. După cum se arată în Tsukiyama et al. (1977) se pot lista toate clicile maximale dintr-un graf într-un timp polinomial pentru fiecare clică generată. Un algoritm ca al acestora, în care timpul de execuție depinde de mărimea ieșirii, este cunoscut ca algoritm dependent de ieșire^⁠(d). Algoritmul lor se bazează pe următoarele două observații, care dau o relație între clicile maximale ale unui graf G dat și clicile maximale ale grafului G \ v format prin eliminarea unui nod arbitrar v din G

:

• Pentru fiecare clică maximală K a lui G \ v, ori K continuă să formeze o clică maximală în G, fie K ⋃ {v formează o clică maximală în G. Prin urmare, G are cel puțin la fel de multe clici maximale ca G \ v .
• Fiecare clică maximală din G care nu conține v este o clică maximală în G \ v, și fiecare clică maximală din G care îl conține pe v poate fi formată dintr-o clică maximală K in G \ v prin adăugarea lui v și prin eliminarea nodurilor neadiacente cu v din K.

Folosind aceste observații, se pot genera toate clicile maximale ale lui G printr-un algoritm recursiv care alege un nod v arbitrar și apoi, pentru fiecare clică maximală K din G \ v, produce K și clica formată prin adăugarea lui v la K și eliminarea nodurilor neadiacente cu v. Cu toate acestea, unele clici ale lui G pot fi generate în acest fel pornind de la mai multe clici-părinte ale lui G \ v, deci trebuie eliminate duplicatele producând la ieșire o clică a lui G doar atunci când părintele său din G \ v este maximul lexicografic dintre toate clicile-părinte posibile. Pe baza acestui principiu, se arată că toate clicile maximale din G pot fi generat în timp O(mn) pe clică, unde m este numărul de muchii din G și n este numărul de noduri. Chiba & Nishizeki (1985) îmbunătățesc acest rezultat până la O(ma) pe clică, unde a este arboricitatea^⁠(d) grafului dat. Makino & Uno (2004) oferă o alternativă de algoritm dependent de ieșire bazat pe înmulțirea rapidă a matricelor. Johnson & Yannakakis (1988) arată că este chiar posibilă listarea tuturor clicilor maxime în ordine lexicografică^⁠(d) cu întârziere polinomială^⁠(d) pe fiecare clică. Cu toate acestea, alegerea ordinii este importantă pentru eficiența acestui algoritm: pentru a inversa acestei ordini, nu există niciun algoritm cu întârziere polinomială decât dacă P = NP.

Pe baza acestui rezultat, este posibilă listarea tuturor clicilor maximale în timp polinomial, pentru familiile de grafuri în care numărul de clici este delimitat polinomial. Aceste familii includ grafuri cordale^⁠(d), grafurile complete, grafurile fără triunghiuri^⁠(d), grafurile de intervale^⁠(d), grafurile de boxicitate^⁠(d) limitată, și grafurile planare. În particular, grafurile planare au O(n) clici, de dimensiune cel mult constantă, care pot fi enumerate într-un timp liniar. Același lucru este valabil pentru orice familie de grafuri, care este atât rară^⁠(d) (are un număr de muchii cel mult liniar proporțional cu numărul de noduri) și închisă în raport cu operațiunea de găsire de subgrafuri.

Găsirea clicilor maxime din grafuri arbitrare

Se poate găsi o clică maximă, sau numărul de clică al unui graf cu n noduri în timp O(3^n/3) = O(1.4422ⁿ) folosind unul dintre algoritmii descriși mai sus pentru a lista toate clicile maximale ale grafului, returnând-o apoi pe cea mai mare. Cu toate acestea, pentru această variantă de problemă a clicilor sunt posibile limite mai bune în cel mai rău caz. Algoritmul lui Tarjan & Trojanowski (1977) rezolvă această problemă în timp O(2^n/3) = O(1.2599ⁿ). Este o schemă de backtracking recursiv similară cu cea din algoritmul Bron–Kerbosch, dar este capabilă să elimine unele apeluri recursive, atunci când se poate demonstra că clicile găsite în apel vor fi suboptime. Jian (1986) a îmbunătățit timpul la O(2^0.304n) = O(1.2346ⁿ), și Robson (1986) la O(2^0.276n) = O(1.2108ⁿ), în detrimentul unei complexități în spațiu mai ridicate. Algoritmul lui Robson combină un sistem backtracking similar (cu o analiză mai complexă a cazului) și o tehnică de programare dinamică^⁠(d) în care soluția optimă este precalculate pentru toate subgrafurile mici conectate ale grafului complementar^⁠(d). Aceste soluții parțiale sunt utilizate pentru a scurtcircuita recursivitatea backtracking. Cel mai rapid algoritm cunoscut astăzi este o versiune a acestei metode îmbunătățită de către Robson (2001) care rulează în timp O(2^0.249n) = O(1.1888ⁿ).

Au existat și cercetări ample pe algoritmi euristici pentru rezolvarea problemelor clicii maxime fără garanții de execuție în cel mai rău caz, bazate pe metode, între care branch and bound^⁠(d), căutare locală^⁠(d), algoritmii greedy, și programarea pe constrângeri^⁠(d). Printre metodologiile nestandard de calcul propuse pentru a găsi clici se numără calculul cu ADN și calculul cuantic adiabatic^⁠(d). Problema clicii maxime a făcut subiectul unei provocări de implementare sponsorizată de DIMACS, în anii 1992-1993, și o colecție de grafuri utilizate ca benchmark pentru provocare este disponibilă public.

Clase speciale de grafuri

În acest graf de permutări, clicile maxime corespund celei mai lungi secvențe descrescătoare (4,3,1) și (4,3,2) ale permutării care îl definește.

Grafurile planare, și alte familii de grafuri rare, au fost discutate mai sus: au un număr liniar de clici maximale, de dimensiuni limitate, care pot fi enumerate într-un timp liniar. În particular, pentru grafuri planare, orice clică poate avea cel mult patru noduri, conform teoremei lui Kuratowski^⁠(d).

Grafurile perfecte^⁠(d) sunt definite prin proprietățile lor că numărul de clică este egal numărul cromatic, și că această egalitate este valabilă și în fiecare subgraf indus. Pentru grafurile perfecte, este posibil să se găsească o clică maximă în timp polinomial, folosind un algoritm bazat pe programarea semidefinită^⁠(d). Cu toate acestea, această metodă este complexă și necombinatorie și algoritmii specializați de găsire a clicilor au fost dezvoltați pentru multe subclase de grafuri perfecte. În grafurile complementare^⁠(d) ale grafurilor bipartite, teorema lui König^⁠(d) permite ca problema clicii maxime să fie rezolvată folosind tehnici de matching^⁠(d). Într-o altă clasă de grafuri perfecte, grafurile de permutări^⁠(d), o clică maximă este una dintre cele mai lungi secvențe descrescătoare^⁠(d) ale permutării care definește graful și pot fi găsite folosind algoritmi cunoscuți pentru problema celei mai lungi secvențe descrescătoare. Invers, fiecare instanță de problemă a celei mai lungi secvențe descrescătoare a unei permutări poate fi descrisă echivalent, ca o problemă de a găsi o clică maximă în graful permutării. Even, Pnueli & Lempel (1972) oferă o alternativă de algoritm în timp pătratic pentru clici maxime în grafuri de comparabilitate^⁠(d), o clasă mai largă de grafuri perfecte care cuprind grafurile de permutări drept caz particular. În grafurile cordale^⁠(d), clicile maxime pot fi găsite prin listarea nodurilor într-o ordine de eliminare, și verificând vecinătățile^⁠(d) de clică ale fiecărui nod în această ordine.

În unele cazuri, acești algoritmi pot fi extinși și la alte clase neperfecte de grafuri. De exemplu, într-un graf circular^⁠(d), vecinătatea fiecărui nod este un graf de permutare, deci o clică maximă într-un graf circular poate fi găsită prin aplicarea algoritmului pentru grafurile de permutări fiecărei vecinătăți. În mod similar, într-o graf de discuri unitare (cu o reprezentare geometrică cunoscută), există un algoritm în timp polinomial pentru clica maximă bazat pe aplicarea algoritmului pentru complementele grafurilor bipartite la vecinătățile comune ale unor perechi de noduri.

Problema algoritmică de a găsi o clică maximă într-un graf aleator^⁠(d) extras din modelul Erdős–Rényi^⁠(d) (în care fiecare muchie apare cu probabilitatea 1/2, independent de celelalte muchii) a fost sugerată de către Karp (1976). Deoarece clica maximă într-un graf aleator are, cu mare probabilitate, dimensiune logaritmică, el poate fi găsit printr-o căutare cu forță brută într-un timp așteptat să fie 2^O(log2n). Deși numărul de clică al unui astfel de graf este, de obicei, foarte aproape de a 2 log₂n, algoritmi greedy simpli dar și tehnici de aproximare randomizate mai sofisticate găsesc numai clici de dimensiune log₂n, de două ori mai mici. Numărul maxim de clici în astfel de grafice este cu mare probabilitate exponențial în raport cu log²n, ceea ce împiedică apariția de metode care listează toate clicile maxime și rulează în timp polinomial. Din cauza dificultății acestei probleme, mai mulți autori au investigat problema clicii plantate^⁠(d) problema, problema clicii pe grafuri aleatoare care au fost extinse prin adăugarea de clici mari. Deși metodele spectrale^⁠(d) și programarea semidefinită^⁠(d) pot detecta clici ascunse de mărime Ω(√n), nu se cunosc algoritmi în timp polinomial care să le detecteze pe cele de mărime o(√n) (exprimat cu notația little o).

Algoritmi de aproximare

Mai mulți autori au considerat algoritmi de aproximare care încearcă să găsească o clică sau o mulțime independentă care, deși nu este maximă, are dimensiuni cât mai aproape de maxim, în timp polinomial. Deși o mare parte din această muncă s-a concentrat pe mulțimi independente în grafuri rare, un caz care nu are sens pentru problema complementară a clicii, s-a lucrat și la algoritmi de aproximare care nu folosesc astfel de prezumții de raritate.

Feige (2004) descrie un algoritm în timp polinomial care găsește o clică de mărimea Ω((log n/log log n)²) în orice graf care are numărul de clică Ω(n/log^kn) pentru orice constantă k. Folosind acest algoritm atunci când numărul de clică al unui graf dat de intrare este între n/log n

și n/log³n, trecând la un alt algoritm al lui Boppana & Halldórsson (1992) pentru grafuri cu numere de clică mai mari, și alegând o clică de două noduri dacă ambii algoritmi nu reușesc să gasească nimic, Feige^⁠(d) oferă un algoritm de aproximare care găsește o clică cu un număr de noduri cu o aproximație de O(n(log log n)²/log³n) față de maxim. Deși raportul de aproximare^⁠(d) al acestui algoritm este slab, este cel mai bun care se cunoaște până în prezent. Rezultatele asupra dificultății de aproximare^⁠(d) descris mai jos sugerează că nu poate exista niciun algoritm de aproximare cu un raport de aproximare semnificativ mai mic decât liniar.

Limite inferioare

NP-completitudinea

Instanță de 3-CNF satisfiabilitate (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) redusă la clică. Nodurile verzi formează o 3-clică și corespunde unei atribuiri satisfăcătoare.

Problema deciziei pe clici este NP-completă. Acesta a fost una dintre cele 21 de probleme ale lui Richard Karp demonstrate a fi NP-complete în lucrarea sa „Reducibility Among Combinatorial Problems” din 1972. Această problemă a fost menționată, și în articolul lui Stephen Cook prin care introducea teoria problemelor NP-complete. Din cauza dificultății problemei deciziei, problema de a găsi o clică maximă este tot NP-hard. Dacă s-ar putea rezolva, s-ar putea rezolva și problema deciziei, prin compararea dimensiunii clicii maxime cu dimensiunea parametrului dat ca intrare în problema deciziei.

Demonstrația de NP-completitudine a lui Karp este o reducere many-one de la problema satisfiabilității booleene. Acesta descrie modul de a traduce formule booleene în formă normală conjunctivă^⁠(d) (CNF) în instanțe echivalente de probleme a clicii maxime. Satisfiabilitatea, la rândul său, a fost demonstrată a fi NP-completă în teorema Cook–Levin^⁠(d). Dintr-o formulă CNF dată, Karp formează un graf care are un nod pentru fiecare pereche (v,c), unde v este o variabilă sau negația ei și c este o clauză din formulă ce conține v. Două dintre aceste noduri sunt conectate printr-o muchie dacă ele reprezintă atribuiri de variabile compatibile pentru diferite clauze. Adică există o muchie de la (v,c) la (u,d) ori de câte ori c ≠ d și u și v nu sunt niciuna negația celeilalte. Dacă k reprezintă numărul de clauze în formula CNF, atunci clicile cu k noduri din acest graf reprezintă moduri consistente de atribuire de valori de adevăr unor din variabilele sale, pentru a satisface formula. Prin urmare, formula poate fi satisfăcută dacă și numai dacă există o clică de k noduri.

Unele probleme NP-complete (cum ar fi problema comis-voiajorului pe grafuri planare) se pot rezolva într-un timp exponențial într-o funcție subliniară față de dimensiunea de parametrului de intrare n, semnificativ mai rapid decât o căutare cu forța brută. Cu toate acestea, este puțin probabil ca o astfel de limită subexponențială de timp să fie posibilă pentru problema clicii pe grafuri arbitrare, deoarece ar implica în mod similar limite subexponențiale pentru multe alte probleme NP-complete standard.

Complexitatea circuitelor

Un circuit monoton care să detecteze o clică de k noduri într-un graf de n noduri pentru k = 3 și {{{1}}}. Fiecare intrare a circuitului codifică prezența ori absența unei anume muchii (cu roșu) din the graf. Circuitul folosește o poartă „și” internă pentru a detecta fiecare potențială k-clică.

Dificultatea computațională a problemei clicii a făcut ca ea să fie folosită la demonstrarea mai multor limite inferioare în complexitatea circuitelor^⁠(d). Existența unei clici de o anume dimensiune este o proprietate monotonă a grafului^⁠(d), adică dacă există o clică într-un graf dat, ea va exista în orice supergraf. Deoarece această proprietate este monotonă, atunci trebuie să existe un circuit monoton, care folosește doar porți „și” și porți „sau”, care să rezolve problema deciziei clicii pentru o dimensiune dată a clicii. Se poate demonstra însă că mărimea acestor circuite este o funcție superpolinomială de numărul de noduri și mărimea clicii, exponențială față de rădăcina cubică a numărului de noduri. Chiar și dacă s-ar permite un număr mic de porți „nu”^⁠(d), complexitatea rămâne superpolinomială. Mai mult, profunzimea unui circuit monoton pentru problema clicii cu porți al căror fan-in^⁠(d) este limitat trebuie să fie cel puțin polinomială în raport cu mărimea clicii.

Complexitatea arborilor de decizie

Un arbore de decizie simplu pentru a detecta prezența unei 3-clici într-un graf cu 4 noduri. Folosește până la 6 întrebări de forma „Există muchia roșie?”, atingând limita optimă n(n − 1)/2.

Complexitatea arborelui de decizie^⁠(d) (determinist) pentru stabilirea unui invariant de graf este numărul de întrebări de forma „există o muchie între nodul u și nodul v?”, căruia trebuie să i se găsească răspunsul în cel mai rău caz, pentru a determina dacă un graf are o anumită proprietate. Adică este adâncimea minimă a unui arbore de decizie boolean asociat problemei. Sunt n(n − 1)/2 întrebări ce pot fi puse. Prin urmare, orice invariant de graf poate fi determinat cu cel mult n(n − 1)/2 întrebări. Este de asemenea posibil să se definească complexitatea unor arbori aleatori și cuantici de decizie pentru un invariant, numărul așteptat de întrebări (pentru datele de intrare din cel mai rău caz) pe care trebuie să-l aibă răspunsul unui studiu aleator sau al unui algoritm cuantic pentru a determina corect dacă graficul dat are invariantul respectiv.

Pentru că proprietatea de a conține o clică este monotonă, ea este acoperită de conjectura Aanderaa–Karp–Rosenberg^⁠(d), care prevede că complexitatea unui arbore de decizie determinist a oricărei proprietăți monotone netriviale a grafului este exact n(n − 1)/2. Pentru invarianți arbitrari monotoni de graf, această ipoteză rămâne nedemonstrată. Cu toate acestea, pentru arbori de decizie determiniști, precum și pentru orice k în intervalul 2 ≤ k ≤ n, proprietatea de a conține o k-clică a fost demonstrată a avea complexitatea arborelui de decizie exact n(n − 1)/2 de către Bollobás (1976). Arborii de decizie determiniști necesită și o dimensiune exponențială pentru detectarea clicilor, sau dimensiuni polinomiale pentru a detecta clici de dimensiune mărginită.

Conjectura Aanderaa–Karp–Rosenberg prevede și că complexitatea arborelui de decizie randomizat a funcțiilor monotone netriviale este Θ(n²). Conjectura rămâne din nou nedemonstrată, dar a fost rezolvată pentru proprietatea de a conține o k clică pentru 2 ≤ k ≤ n. Această proprietate este cunoscută a avea un arbore de decizie randomizat de complexitate Θ(n²). Pentru arbori de decizie cuantici, cea mai cunoscută limită inferioară este Ω(n), dar nu se cunoaște niciun algoritm de potrivire pentru cazul k ≥ 3.

Intractabilitatea cu parametru fix

Complexitatea parametrizată^⁠(d) este studierea în cadrul teoriei complexității a problemelor care sunt în mod natural echipate cu un mic parametru întreg k și pentru care problema devine mai dificilă dacă k crește, cum ar fi găsirea de k-clici în grafuri. O problemă este declarată a fi tractabilă cu parametru fix dacă există un algoritm pentru rezolvarea ei pe intrări de dimensiune n, și o funcție f, astfel că algoritmul se execută în timp f(k) n^O(1). Adică este tractabilă cu parametru fix dacă poate fi rezolvată în timp polinomial pentru orice valoare fixă a lui k și mai mult decât atât, dacă exponentul polinomului nu depinde de k.

Pentru a găsi clicile de k noduri, algoritmul de căutare cu forța brută are timp de rulare O(n^kk²). Deoarece exponentul lui n depinde de k, acest algoritm nu este tractabil cu parametru fix. Deși aceasta poate fi îmbunătățit cu ajutorul înmulțirii rapide a matricelor, timpul de rulare are încă un exponent care este liniară în k. Astfel, deși timpul de rulare al unor algoritmi cunoscuți pentru problema clicii este polinomial pentru orice k fix, acești algoritmi nu sunt suficienți pentru tractabilitatea cu parametru fix. Downey & Fellows (1995) au definit o ierarhie a problemelor parametrizate, ierarhia W, despre care au emis ipoteza că nu are algoritmi tractabili cu parametru fix. Ei au demonstrat că mulțimea independentă (sau, echivalent, clica) este problemă dură pentru primul nivel al acestei ierarhii, W[1]. Astfel, conform acestei conjuncturi, clica nu are niciun algoritm tractabil cu parametru fix. Mai mult decât atât, acest rezultat oferă baza pentru demonstrația W[1]-durității multor alte probleme, și astfel servește ca un analog al teoremei Cook–Levin^⁠(d) pentru complexitatea parametrizată.

Chen et al. (2006) au arătat că găsirea de clici cu k noduri nu poate fi efectuată în timp n^o(k) cu excepția cazului în care nu este valabilă ipoteza timpului exponențial^⁠(d). Din nou, aceasta oferă dovezi că nu este posibil niciun algoritm tractabil cu parametru fix.

Deși problemele de listare a clicilor maximale sau găsirea unor clici maxime sunt puțin probabil să tractabile cu parametrul fix k, acestea pot fi tractabile cu alți parametri ficși. De exemplu, ambele probleme sunt cunoscute a fi tractabile cu parametru fix atunci când sunt parametrizate prin degenerarea^⁠(d) grafului de la intrare.

Greutatea de aproximare

Un graf de relații de compatibilitate între eșantioane de 2 biți din șiruri de 3 biți. Fiecare clică maximală (triunghi) din acest graf reprezintă toate modalitățile de eșantionare a unui singur șir de 3 biți. Demonstrația neaproximabilității problemei clicii implică subgrafuri induse ale unor grafuri definite analog pentru un număr mai mare de biți.

Se cunosc demult rezultate slabe care sugerează problema clicii ar putea fi greu de aproximat. Garey & Johnson (1978) au observat că, din cauza faptului că numărul de clică are valori întregi mici și este NP-dur de calculat, acesta nu poate avea o schemă de aproximare în timp polinomial complet^⁠(d). Dacă ar fi disponibilă o aproximare prea precisă, rotunjirea valorii acesteia la un număr întreg ar da exact numărul de clică. Cu toate acestea, nu se cunoșteau prea multe până la începutul anilor 1990, atunci când mai mulți autori au început să facă conexiuni între aproximarea clicilor maxime și demonstrațiile probabilistic verificabile^⁠(d). Ei au folosit aceste conexiuni pentru a dovedi dificultatea de aproximare^⁠(d) a rezultatelor pentru problema clicii maxime. După mai multe îmbunătățiri ale acestor rezultate, se cunoaște că, pentru orice număr real ε > 0, nu poate exista un algoritm în timp polinomial care aproximează clica maximă cu un factor mai bun decât O(n^1 − ε), decât dacă P = NP.

Ideea acestor rezultate de neaproximabilitate este de a forma un graf care reprezintă un sistem de demonstrații probabilistic verificabile pentru o problemă NP-completă, cum ar fi problema satisfiabilității booleene. Într-un sistem de demonstrații veridicabile probabilistic, o demonstrație este reprezentată ca o succesiune de biți. Un exemplu de problemă a satisfiabilității ar trebui să aibă o demonstrație validă dacă și numai dacă este satisfiabilă. Demonstrația este verificată de către un algoritm care, după un timp polinomial de calcul pe datele de intrare ale problemei satisfiabilității, alege să examineze un număr mic de poziții alese aleatoriu din șirul demonstrației. În funcție de ce valori sunt găsite la proba de biți, verificatorul va accepta sau va respinge o demonstrație, fără să se mai uite la restul de biți. Falsele negative nu sunt permise: o demonstrație validă trebuie să fie întotdeauna acceptată. Cu toate acestea, acceptarea unei demonstrații invalide în mod eronat poate fi acceptată. Pentru fiecare demonstrație invalidă, probabilitatea ca verificatorul să o accepte trebuie să fie scăzută.

Pentru a transforma un sistem de demonstrații probabilistic verificabile într-o problemă a clicii, se formează un graf cu un nod pentru fiecare rulare posibil acceptabilă de către verificatorul de demonstrații. Adică un nod este definit ca fiind una dintre posibilele alegeri aleatorii din mulțimea de poziții de examinat, și de valorile biților pentru acele poziții care ar face ca verificatorul să accepte demonstrația. Două noduri sunt adiacente, în acest graf, dacă cele două rulări acceptate corespunzătoare văd aceleași valori de biți biți la fiecare poziție examinată de fiecare. Fiecare șir de demonstrație (validă sau invalidă) corespunde unei clici, mulțimea rulărilor acceptate care văd acel șir de demonstrare, și toate clicile maximale apar în acest fel. Una dintre aceste clici este mare, dacă și numai dacă ea corespunde unui șir de demonstrație acceptat de mulți verificatori. Dacă instanța originală de satisfiabilitate este satisfiabilă, aceasta va fi un șir de demonstrație valid, unul acceptabil de către toate rulările verificatorului, și acest șir va corespunde unei clici mari din graf. Cu toate acestea, în cazul în care originalul nu este satisfiabil, atunci toate șirurile de demonstrație sunt invalide, fiecare șir de demonstrație având doar un număr mic de rulări ale verificatorului care-l acceptă eronat, și toate clicile sunt mici. Prin urmare, dacă s-ar putea distinge în timp polinomial între grafurile care au clici mari și grafurile în care toate clicile sunt mici, sau dacă s-ar putea aproxima cu exactitate problema clicii, atunci aplicând această aproximare la grafurile generate de cazurile de satisfiabilitate ar permite distingerea cazurilor satisfiabile de cele nesatisfiabile. Cu toate acestea, acest lucru nu este posibil decât dacă P = NP.

Bibliografie

Tratate și manuale

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4 .
• Blair, Jean R. S.; Peyton, Barry (1993), „An introduction to chordal graphs and clique trees”, Graph theory and sparse matrix computation, IMA Vol. Math. Appl., 56, Springer, New York, pp. 1–29, doi:10.1007/978-1-4613-8369-7_1, MR 1320296 .
• Bomze, I. M.; Budinich, M.; Pardalos, P. M.; Pelillo, M. (1999), „The maximum clique problem”, Handbook of Combinatorial Optimization, 4, Kluwer Academic Publishers, pp. 1–74, CiteSeerX 10.1.1.48.4074  .
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „34.5.1 The clique problem”, Introduction to Algorithms (ed. 2nd), MIT Press and McGraw-Hill, pp. 1003–1006, ISBN 0-262-03293-7 .
• Downey, R. G.; Fellows, M. R. (1999), Parameterized complexity, Springer-Verlag, ISBN 0-387-94883-X .
• Golumbic, M. C. (1980), Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, ISBN 0-444-51530-5 .
• Grötschel, M.; Lovász, L.; Schrijver, A. (1988), „9.4 Coloring Perfect Graphs”, Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, 2, Springer-Verlag, pp. 296–298, ISBN 0-387-13624-X .
• Gutin, G. (2004), „5.3 Independent sets and cliques”, În Gross, J. L.; Yellen, J., Handbook of graph theory, Discrete Mathematics & Its Applications, CRC Press, pp. 389–402, ISBN 978-1-58488-090-5 .
• Muegge, Ingo; Rarey, Matthias (2001), „Small molecule docking and scoring”, Reviews in Computational Chemistry, 17: 1–60, doi:10.1002/0471224413.ch1 .
• National Research Council Committee on Mathematical Challenges from Computational Chemistry (1995), Mathematical Challenges from Theoretical/Computational Chemistry, National Academies Press, doi:10.17226/4886 .
• Pelillo, Marcello (2009), „Heuristics for maximum clique and independent set”, Encyclopedia of Optimization, Springer, pp. 1508–1520, doi:10.1007/978-0-387-74759-0_264 .
• Plummer, Michael D. (1993), „Well-covered graphs: a survey”, Quaestiones Mathematicae, 16 (3): 253–287, doi:10.1080/16073606.1993.9631737, MR 1254158, arhivat din original la 27 mai 2012, accesat în 31 mai 2017  .
• Sipser, M. (1996), Introduction to the Theory of Computation, International Thompson Publishing, ISBN 0-534-94728-X .
• Skiena, Steven S. (2009), The Algorithm Design Manual (ed. 2nd), Springer, ISBN 978-1-84800-070-4 .
• Valiente, Gabriel (2002), „Chapter 6: Clique, Independent Set, and Vertex Cover”, Algorithms on Trees and Graphs, Springer, pp. 299–350, doi:10.1007/978-3-662-04921-1_6 .
• Wasserman, Stanley; Faust, Katherine (1994), Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences, 8, Cambridge University Press, p. 276, ISBN 978-0-521-38707-1 .

Presa populară

• Kolata, Gina (26 iunie 1990), „In a Frenzy, Math Enters Age of Electronic Mail”, New York Times .

Articole de cercetare

• Abello, J.; Pardalos, P. M.; Resende, M. G. C. (1999), „On maximum clique problems in very large graphs” (PDF), În Abello, J.; Vitter, J., External Memory Algorithms, DIMACS Series on Discrete Mathematics and Theoretical Computer Science, 50, American Mathematical Society, pp. 119–130, ISBN 0-8218-1184-3, arhivat din original (PDF) la 16 ianuarie 2017, accesat în 31 mai 2017 .
• Alon, N.; Boppana, R. (1987), „The monotone circuit complexity of boolean functions”, Combinatorica, 7 (1): 1–22, doi:10.1007/BF02579196 .
• Alon, N.; Krivelevich, M.; Sudakov, B. (1998), „Finding a large hidden clique in a random graph”, 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), „Finding and counting given length cycles”, Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, pp. 354–364 .
• Amano, Kazuyuki; Maruoka, Akira (2005), „A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log log N negation gates”, 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), „Proof verification and the hardness of approximation problems”, Journal of the ACM, 45 (3): 501–555, doi:10.1145/278298.278306, Format:ECCC . Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267823.
• Arora, S.; Safra, S. (1998), „Probabilistic checking of proofs: A new characterization of NP”, Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901 . Originally presented at the 1992 Symposium on Foundations of Computer Science, doi:10.1109/SFCS.1992.267824.
• Balas, E.; Yu, C. S. (1986), „Finding a maximum clique in an arbitrary graph”, SIAM Journal on Computing, 15 (4): 1054–1068, doi:10.1137/0215075 .
• Barrow, H.; Burstall, R. (1976), „Subgraph isomorphism, matching relational structures and maximal cliques”, Information Processing Letters, 4 (4): 83–84, doi:10.1016/0020-0190(76)90049-1 .
• Battiti, R.; Protasi, M. (2001), „Reactive local search for the maximum clique problem”, Algorithmica, 29 (4): 610–637, doi:10.1007/s004530010074 .
• Bollobás, Béla (1976), „Complete subgraphs are elusive”, 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, M. M. (1992), „Approximating maximum independent sets by excluding subgraphs”, BIT Numerical Mathematics, 32 (2): 180–196, doi:10.1007/BF01994876 .
• Bron, C.; Kerbosch, J. (1973), „Algorithm 457: finding all cliques of an undirected graph”, Communications of the ACM, 16 (9): 575–577, doi:10.1145/362342.362367 .
• Carraghan, R.; Pardalos, P. M. (1990), „An exact algorithm for the maximum clique problem”, Operations Research Letters, 9 (6): 375–382, doi:10.1016/0167-6377(90)90057-C .
• Cazals, F.; Karande, C. (2008), „A note on the problem of reporting maximal cliques” (PDF), Theoretical Computer Science, 407 (1): 564–568, doi:10.1016/j.tcs.2008.05.010 ^{[nefuncțională]}.
• Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), „Strong computational lower bounds via parameterized complexity”, Journal of Computer and System Sciences, 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007 
• Chiba, N.; Nishizeki, T. (1985), „Arboricity and subgraph listing algorithms”, SIAM Journal on Computing, 14 (1): 210–223, doi:10.1137/0214017 .
• Childs, A. M.; Farhi, E.; Goldstone, J.; Gutmann, S. (2002), „Finding cliques by quantum adiabatic evolution” (PDF), Quantum Information and Computation, 2 (3): 181–191, arXiv:quant-ph/0012104  ^{[nefuncțională]}.
• Childs, A. M.; Eisenberg, J. M. (2005), „Quantum algorithms for subset finding”, Quantum Information and Computation, 5 (7): 593–604, arXiv:quant-ph/0311038  .
• Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990), „Unit disk graphs”, Discrete Mathematics, 86 (1–3): 165–177, doi:10.1016/0012-365X(90)90358-O 
• Cook, S. A. (1971), „The complexity of theorem-proving procedures”, Proc. 3rd ACM Symposium on Theory of Computing, pp. 151–158, doi:10.1145/800157.805047 .
• Cook, Stephen A. (1985), „A taxonomy of problems with fast parallel algorithms”, Information and Control, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3, MR 0837088 .
• Day, William H. E.; Sankoff, David (1986), „Computational complexity of inferring phylogenies by compatibility”, Systematic Zoology, 35 (2): 224–229, doi:10.2307/2413432, JSTOR 2413432 .
• Downey, R. G.; Fellows, M. R. (1995), „Fixed-parameter tractability and completeness. II. On completeness for W[1]”, Theoretical Computer Science, 141 (1–2): 109–131, doi:10.1016/0304-3975(94)00097-3 .
• Eisenbrand, F.; Grandoni, F. (2004), „On the complexity of fixed parameter clique and dominating set”, Theoretical Computer Science, 326 (1–3): 57–67, doi:10.1016/j.tcs.2004.05.009 .
• Eppstein, David; Löffler, Maarten; Strash, Darren (2013), „Listing all maximal cliques in large sparse real-world graphs in near-optimal time”, Journal of Experimental Algorithmics, 18 (3): 3.1, doi:10.1145/2543629 .
• Erdős, Paul; Szekeres, George (1935), „A combinatorial problem in geometry” (PDF), Compositio Mathematica, 2: 463–470 .
• Even, S.; Pnueli, A.; Lempel, A. (1972), „Permutation graphs and transitive graphs”, Journal of the ACM, 19 (3): 400–410, doi:10.1145/321707.321710 .
• Fahle, T. (2002), „Simple and fast: Improving a branch-and-bound algorithm for maximum clique”, Proc. 10th European Symposium on Algorithms, Lecture Notes in Computer Science, 2461, Springer-Verlag, pp. 47–86, doi:10.1007/3-540-45749-6_44, ISBN 978-3-540-44180-9 .
• Feige, U. (2004), „Approximating maximum clique by removing subgraphs”, 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), „Approximating clique is almost NP-complete”, Proc. 32nd IEEE Symp. on Foundations of Computer Science, pp. 2–12, doi:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0 .
• Feige, U.; Krauthgamer, R. (2000), „Finding and certifying a large hidden clique in a semirandom graph”, 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), „Markov graphs”, Journal of the American Statistical Association, 81 (395): 832–842, doi:10.2307/2289017, JSTOR 2289017, MR 0860518 .
• Garey, M. R.; Johnson, D. S. (1978), „"Strong" NP-completeness results: motivation, examples and implications”, Journal of the ACM, 25 (3): 499–508, doi:10.1145/322077.322090 .
• Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1976), „Some simplified NP-complete graph problems”, Theoretical Computer Science, 1 (3): 237–267, doi:10.1016/0304-3975(76)90059-1, MR 0411240 .
• Gavril, F. (1973), „Algorithms for a maximum clique and a maximum independent set of a circle graph”, Networks, 3 (3): 261–273, doi:10.1002/net.3230030305 .
• Goldmann, M.; Håstad, J. (1992), „A simple lower bound for monotone clique using a communication game”, Information Processing Letters, 41 (4): 221–226, doi:10.1016/0020-0190(92)90184-W .
• Gröger, Hans Dietmar (1992), „On the randomized complexity of monotone graph properties” (PDF), Acta Cybernetica, 10 (3): 119–127, arhivat din original (PDF) la 24 septembrie 2015, accesat în 2 octombrie 2009 
• Grosso, A.; Locatelli, M.; Della Croce, F. (2004), „Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem”, Journal of Heuristics, 10 (2): 135–152, doi:10.1023/B:HEUR.0000026264.51747.7f .
• Halldórsson, M. M. (2000), „Approximations 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, J. H. (1998), „Test set compaction algorithms for combinational circuits”, Proc. 1998 IEEE/ACM International Conference on Computer-Aided Design, pp. 283–289, doi:10.1145/288548.288615 .
• Harary, F.; Ross, I. C. (1957), „A procedure for clique detection using the group matrix”, Sociometry, American Sociological Association, 20 (3): 205–215, doi:10.2307/2785673, JSTOR 2785673, MR 0110590 .
• Håstad, J. (1999), „Clique is hard to approximate within n^{1 − ε}”, Acta Mathematica, 182 (1): 105–142, doi:10.1007/BF02392825 .
• Impagliazzo, R.; Paturi, R.; Zane, F. (2001), „Which problems have strongly exponential complexity?”, Journal of Computer and System Sciences, 63 (4): 512–530, doi:10.1006/jcss.2001.1774 .
• Itai, A.; Rodeh, M. (1978), „Finding a minimum circuit in a graph”, SIAM Journal on Computing, 7 (4): 413–423, doi:10.1137/0207033 .
• Jerrum, M. (1992), „Large cliques elude the Metropolis process”, Random Structures and Algorithms, 3 (4): 347–359, doi:10.1002/rsa.3240030402 .
• Jian, T (1986), „An O(2^0.304n) algorithm for solving maximum independent set problem”, IEEE Transactions on Computers, IEEE Computer Society, 35 (9): 847–851, doi:10.1109/TC.1986.1676847, ISSN 0018-9340 .
• Johnson, D. S.; Trick, M. A., ed. (1996), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 26, American Mathematical Society, ISBN 0-8218-6609-5 .
• Johnson, D. S.; Yannakakis, M. (1988), „On generating all maximal independent sets”, Information Processing Letters, 27 (3): 119–123, doi:10.1016/0020-0190(88)90065-8 .
• Karp, Richard M. (1972), „Reducibility among combinatorial problems”, În Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (PDF), New York: Plenum, pp. 85–103, arhivat din original (PDF) la 29 iunie 2011, accesat în 31 mai 2017  .
• Karp, Richard M. (1976), „Probabilistic analysis of some combinatorial search problems”, În Traub, J. F., Algorithms and Complexity: New Directions and Recent Results, New York: Academic Press, pp. 1–19 .
• Katayama, K.; Hamamoto, A.; Narihisa, H. (2005), „An effective local search for the maximum clique problem”, Information Processing Letters, 95 (5): 503–511, doi:10.1016/j.ipl.2005.05.010 .
• Khot, S. (2001), „Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring”, Proc. 42nd IEEE Symp. Foundations of Computer Science, pp. 600–609, doi:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3 .
• Kloks, T.; Kratsch, D.; Müller, H. (2000), „Finding and counting small induced subgraphs efficiently”, Information Processing Letters, 74 (3–4): 115–121, doi:10.1016/S0020-0190(00)00047-8 .
• Konc, J.; Janežič, D. (2007), „An improved branch and bound algorithm for the maximum clique problem” (PDF), MATCH Communications in Mathematical and in Computer Chemistry, 58 (3): 569–590 . Source code
• Kuhl, F. S.; Crippen, G. M.; Friesen, D. K. (1983), „A combinatorial algorithm for calculating ligand binding”, Journal of Computational Chemistry, 5 (1): 24–34, doi:10.1002/jcc.540050105 .
• Lagarias, Jeffrey C.; Shor, Peter W. (1992), „Keller's cube-tiling conjecture is false in high dimensions”, Bulletin of the American Mathematical Society, New Series, 27 (2): 279–283, doi:10.1090/S0273-0979-1992-00318-X, MR 1155280 .
• Lipton, R. J.; Tarjan, R. E. (1980), „Applications of a planar separator theorem”, SIAM Journal on Computing, 9 (3): 615–627, doi:10.1137/0209046 .
• Liu, Yu; Lu, Jiaheng; Yang, Hua; Xiao, Xiaokui; Wei, Zhewei (2015), „Towards maximum independent sets on massive graphs”, Proceedings of the 41st International Conference on Very Large Data Bases (VLDB 2015), Proceedings of the VLDB Endowment, 8 (13), pp. 2122–2133, doi:10.14778/2831360.2831366 .
• Luce, R. Duncan; Perry, Albert D. (1949), „A method of matrix analysis of group structure”, Psychometrika, 14 (2): 95–116, doi:10.1007/BF02289146, PMID 18152948 .
• Mackey, John (2002), „A cube tiling of dimension eight with no facesharing”, Discrete and Computational Geometry, 28 (2): 275–279, doi:10.1007/s00454-002-2801-9, MR 1920144 .
• Magniez, Frédéric; Santha, Miklos; Szegedy, Mario (2007), „Quantum algorithms for the triangle problem”, SIAM Journal on Computing, 37 (2): 413–424, arXiv:quant-ph/0310134 , doi:10.1137/050643684 .
• Makino, K.; Uno, T. (2004), „New algorithms for enumerating all maximal cliques”, Algorithm Theory: SWAT 2004, Lecture Notes in Computer Science, 3111, Springer-Verlag, pp. 260–272, 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), New York, NY, USA: ACM, pp. 87–96, arXiv:1503.06447 , doi:10.1145/2746539.2746600, ISBN 978-1-4503-3536-2 .
• Moon, J. W.; Moser, L. (1965), „On cliques in graphs”, Israel Journal of Mathematics, 3: 23–28, doi:10.1007/BF02760024, MR 0182577 .
• Nešetřil, J.; Poljak, S. (1985), „On the complexity of the subgraph problem”, Commentationes Mathematicae Universitatis Carolinae, 26 (2): 415–419 .
• Östergård, P. R. J. (2002), „A fast algorithm for the maximum clique problem”, Discrete Applied Mathematics, 120 (1–3): 197–207, doi:10.1016/S0166-218X(01)00290-6 .
• Ouyang, Q.; Kaplan, P. D.; Liu, S.; Libchaber, A. (1997), „DNA solution of the maximal clique problem”, Science, 278 (5337): 446–449, doi:10.1126/science.278.5337.446, PMID 9334300 .
• Papadimitriou, Christos H.; Yannakakis, Mihalis (1981), „The clique problem for planar graphs”, Information Processing Letters, 13 (4–5): 131–133, doi:10.1016/0020-0190(81)90041-7, MR 0651460 .
• Pardalos, P. M.; Rogers, G. P. (1992), „A branch and bound algorithm for the maximum clique problem”, Computers & Operations Research, 19 (5): 363–375, doi:10.1016/0305-0548(92)90067-F .
• Razborov, A. A. (1985), „Lower bounds for the monotone complexity of some Boolean functions”, Proceedings of the USSR Academy of Sciences (în Russian), 281: 798–801. English translation in Sov. Math. Dokl. 31 (1985): 354–357 Mentenanță CS1: Limbă nerecunoscută (link) .
• Régin, J.-C. (2003), „Using constraint programming to solve the maximum clique problem”, Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003, Lecture Notes in Computer Science, 2833, Springer-Verlag, pp. 634–648, doi:10.1007/978-3-540-45193-8_43 .
• Rhodes, Nicholas; Willett, Peter; Calvet, Alain; Dunbar, James B.; Humblet, Christine (2003), „CLIP: similarity searching of 3D databases using clique detection”, Journal of Chemical Information and Computer Sciences, 43 (2): 443–448, doi:10.1021/ci025605o, PMID 12653507 .
• Robson, J. M. (1986), „Algorithms for maximum independent sets”, Journal of Algorithms, 7 (3): 425–440, doi:10.1016/0196-6774(86)90032-5 .
• Robson, J. M. (2001), Finding a maximum independent set in time O(2^n/4) .
• Rosgen, B; Stewart, L (2007), „Complexity results on graphs with few cliques”, Discrete Mathematics and Theoretical Computer Science, 9 (1): 127–136 .
• Samudrala, Ram; Moult, John (1998), „A graph-theoretic algorithm for comparative modeling of protein structure”, Journal of Molecular Biology, 279 (1): 287–302, doi:10.1006/jmbi.1998.1689, PMID 9636717 .
• Sethuraman, Samyukta; Butenko, Sergiy (2015), „The maximum ratio clique problem”, Computational Management Science, 12 (1): 197–218, doi:10.1007/s10287-013-0197-z, MR 3296231 .
• Song, Y. (2015), „On the independent set problem in random graphs”, International Journal of Computer Mathematics, 92 (11): 2233–2242, doi:10.1080/00207160.2014.976210 .
• Spirin, Victor; Mirny, Leonid A. (2003), „Protein complexes and functional modules in molecular networks”, Proceedings of the National Academy of Sciences, 100 (21): 12123–12128, doi:10.1073/pnas.2032324100, PMC 218723 , PMID 14517352 .
• Tarjan, R. E.; Trojanowski, A. E. (1977), „Finding a maximum independent set” (PDF), SIAM Journal on Computing, 6 (3): 537–546, doi:10.1137/0206038 .
• Tomita, E.; Kameda, T. (2007), „An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments”, Journal of Global Optimization, 37 (1): 95–111, doi:10.1007/s10898-006-9039-7 .
• Tomita, E.; Seki, T. (2003), „An efficient branch-and-bound algorithm for finding a maximum clique”, Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, 2731, Springer-Verlag, pp. 278–289, doi:10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4 .
• Tomita, E.; Tanaka, A.; Takahashi, H. (2006), „The worst-case time complexity for generating all maximal cliques and computational experiments”, Theoretical Computer Science, 363 (1): 28–42, doi:10.1016/j.tcs.2006.06.015 .
• Tsukiyama, S.; Ide, M.; Ariyoshi, I.; Shirakawa, I. (1977), „A new algorithm for generating all the maximal independent sets”, SIAM Journal on Computing, 6 (3): 505–517, doi:10.1137/0206036 .
• Valiant, L. G. (1983), „Exponential lower bounds for restricted monotone circuits”, Proc. 15th ACM Symposium on Theory of Computing, pp. 110–117, doi:10.1145/800061.808739, ISBN 0-89791-099-0 .
• Vassilevska, V.; Williams, R. (2009), „Finding, minimizing, and counting weighted subgraphs”, Proc. 41st ACM Symposium on Theory of Computing, pp. 455–464, doi:10.1145/1536414.1536477, ISBN 978-1-60558-506-2 .
• Wegener, I. (1988), „On the complexity of branching programs and decision trees for clique functions”, Journal of the ACM, 35 (2): 461–472, doi:10.1145/42282.46161 .
• 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), „Linear degree extractors and the inapproximability of max clique and chromatic number”, Proc. 38th ACM Symp. Theory of Computing, pp. 681–690, doi:10.1145/1132516.1132612, ISBN 1-59593-134-1, Format:ECCC .