miniatura|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. Î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.
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 cât și . Ș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 . 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, grupuri de oameni care se cunosc unul pe altul. 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 ,; . 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 . A se vedea, de exemplu, , o lucrare timpurie privind complexitatea în cel mai rău caz a problemei clicii maxime. De asemenea, în 1970, începând cu munca lui si , 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 , 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 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 ș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 pentru a reduce problema găsirii cele a două grafuri la problema de găsirii unei clici maxime în produsul lor.
În , 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 , și pentru găsirea grupurilor de proteine care interacționează strâns. Listarea clicilor într-un este un pas important în analiza anumitor procese aleatoare. În matematică, din mozaicarea față-în-față a hipercuburilor a fost infirmată de , care a folosit un algoritm de găsire a clicilor pe un graf asociat pentru a identifica un contraexemplu.Graful Keller utilizat de are 1048576 de noduri și mărimea clicii 1024.
Definiții miniatura|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 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ă 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 -clicii, la intrare este un graf neorientat și un număr . Rezultatul este o clică cu noduri, dacă există una, sau, în caz contrar, o valoare specială care indică faptul că nu există nici o -clică. În unele variante ale acestei probleme, rezultatul ar trebui să listeze toate clicile de dimensiune . În problema deciziei clicii, la intrare este un graf neorientat și un număr , iar rezultatul este o valoare logică: „adevărat” dacă graful conține o -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 sunt complementare: o clică în G este o mulțime independentă în al lui G și vice-versa., Exercise 34-1, p. 1018. 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ă.See, e.g., . 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 unor , î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., p. 526. 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 (cea găsită de către algoritmul de mai sus) a fost demonstrată a fi pentru clasa funcțiilor în timp polinomial. Acest rezultat sugerează că problema este puțin probabil să fie rezolvată în clasa de complexitate paralelă .
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 . Acest algoritm analizează fiecare subgraf cu k noduri și verifică dacă formează o clică. Este nevoie de timp , exprimat în notația big O. Aceasta pentru că există subgrafuri de verificat, fiecare având 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.E.g., see .