Problemă cu clica - Clique problem

Algoritmul forță brută găsește un 4-clică în acest grafic 7-vertex (complementul 7-vertex Graficul cale ) prin verificarea în mod sistematic toate C (7,4) = 35 subgrafurilor 4-vertex pentru completitudine.

În informatică , problema clică este problema de calcul a găsirii clicurilor (subseturi de vârfuri, toate adiacente unele cu altele, numite și subgrafe complete ) într-un grafic . Are mai multe formulări diferite, în funcție de care clici și ce informații ar trebui să fie găsite. Formulările obișnuite ale problemei clici includ găsirea unei clici maxime (o clică cu cel mai mare număr posibil de vârfuri), găsirea unei clici de greutate maximă într-un grafic ponderat, listarea tuturor clici maxime (clici care nu pot fi mărite) și rezolvarea problemei deciziei. de a testa dacă un grafic conține o clică mai mare decât o dimensiune dată.

Problema clică apare în următoarea situație din lumea reală. Luați în considerare o rețea socială , în care vârfurile graficului reprezintă oameni, iar marginile graficului reprezintă cunoștințe reciproce. Apoi, o clică reprezintă un subset de oameni care se cunosc cu toții, iar algoritmii pentru găsirea unor clici pot fi folosiți pentru a descoperi aceste grupuri de prieteni comuni. Împreună cu aplicațiile sale în rețelele de socializare, problema clică are, de asemenea, multe aplicații în bioinformatică și chimie computațională .

Majoritatea versiunilor problemei clici sunt dificile. Problema deciziei de clică este NP-completă (una dintre cele 21 de probleme Karp-NP-complete ). Problema de a găsi clica maximă este atât de fixă cu parametri fixi, cât și greu de aproximat . Și, listarea tuturor clicurilor maxime poate necesita timp exponențial, deoarece există grafice cu multe clicuri maxime exponențial. Prin urmare, o mare parte din teoria despre problema clică este dedicată identificării tipurilor speciale de grafice care admit algoritmi mai eficienți sau stabilirii dificultății de calcul a problemei generale în diferite modele de calcul.

Pentru a găsi o clică maximă, se pot inspecta sistematic toate subseturile, dar acest tip de căutare cu forță brută necesită prea mult timp pentru a fi practic pentru rețelele care cuprind mai mult de câteva zeci de vârfuri. Deși nu se cunoaște niciun algoritm de timp polinomial pentru această problemă, sunt cunoscuți algoritmi mai eficienți decât căutarea cu forță brută. De exemplu, algoritmul Bron – Kerbosch poate fi folosit pentru a enumera toate clice maxime în cel mai rău timp optim și este, de asemenea, posibil să le listăm în timp polinomial pe clică.

Istorie și aplicații

Studiul subgrafelor complete în matematică precede terminologia „clică”. De exemplu, subgrafele complete fac o apariție timpurie în literatura matematică în reformularea teoretică a graficului a teoriei Ramsey de Erdős & Szekeres (1935) . Dar termenul „clică” și problema listării algoritmice a clicurilor provin ambele din științele sociale, unde subgrafele complete sunt folosite pentru a modela clici sociale , grupuri de oameni care se cunosc toți. Luce & Perry (1949) au folosit grafice pentru a modela rețelele sociale și au adaptat terminologia științelor sociale la teoria graficelor. Au fost primii care au numit subgrafele complete „clici”. Primul algoritm pentru rezolvarea problemei clici este cel al lui Harary & Ross (1957) , care au fost motivați de aplicația sociologică. Cercetătorii în științe sociale au definit, de asemenea, diferite alte tipuri de clici și clici maxime în rețeaua socială, „subgrupuri coezive” de oameni sau actori din rețea, toți împărtășind unul dintre mai multe tipuri diferite de relații de conectivitate. Multe dintre aceste noțiuni generalizate de clici pot fi, de asemenea, găsite prin construirea unui grafic neorientat ale cărui margini reprezintă perechi de actori din rețeaua socială și apoi aplicarea unui algoritm pentru problema clicii acestui grafic.

De la lucrările lui Harary și Ross, mulți alții au conceput algoritmi pentru diferite versiuni ale problemei clici. În anii 1970, cercetătorii au început să studieze acești algoritmi din punctul de vedere al analizei în cel mai rău caz . A se vedea, de exemplu, Tarjan și Trojanowski (1977) , o lucrare timpurie asupra complexității celei mai nefavorabile a problemei maximei clici. De asemenea, în anii 1970, începând cu lucrările lui Cook (1971) și Karp (1972) , cercetătorii au început să utilizeze teoria completitudinii NP și a rezultatelor legate de intractabilitate pentru a oferi o explicație matematică pentru dificultatea percepută a problemei clici. În anii 1990, o serie revoluționară de lucrări începând cu Feige și colab. (1991) și raportat în New York Times , au arătat că (presupunând P ≠ NP ) nu este nici măcar posibil să se aproximeze problema cu precizie și eficiență.

Algoritmi de găsire a clichelor au fost folosiți în chimie , pentru a găsi substanțe chimice care se potrivesc cu o structură țintă și pentru a modela andocarea moleculară și locurile de legare ale reacțiilor chimice. Ele pot fi, de asemenea, utilizate pentru a găsi structuri similare în cadrul diferitelor molecule. În aceste aplicații, se formează un grafic în care fiecare vârf reprezintă o pereche potrivită de atomi, câte unul din fiecare dintre cele două molecule. Două vârfuri sunt conectate printr-o margine dacă potrivirile pe care le reprezintă sunt compatibile între ele. A fi compatibil poate însemna, de exemplu, că distanțele dintre atomii din cele două molecule sunt aproximativ egale, cu o anumită toleranță dată. O clică din acest grafic reprezintă un set de perechi de atomi potrivite în care toate meciurile sunt compatibile între ele. Un caz special al acestei metode este utilizarea produsului modular de grafice pentru a reduce problema găsirii subgrafului maxim indus comun de două grafice la problema găsirii unei clici maxime în produsul lor.

În generarea automată a modelelor de testare , găsirea unor clici poate ajuta la legarea dimensiunii unui set de testare. În bioinformatică , algoritmii de identificare a clicurilor au fost folosiți pentru a deduce arborii evolutivi , pentru a prezice structurile proteinelor și pentru a găsi grupuri de proteine ​​care interacționează îndeaproape. Listarea clicurilor într-un grafic de dependență este un pas important în analiza anumitor procese aleatorii. În matematică, conjectura lui Keller asupra plăcilor față în față a hipercuburilor a fost respinsă de Lagarias și Shor (1992) , care au folosit un algoritm de găsire a clicurilor pe un grafic asociat pentru a găsi un contraexemplu.

Definiții

Graficul prezentat are o clică maximă, triunghiul {1,2,5} și încă patru clici maxime, perechile {2,3}, {3,4}, {4,5} și {4,6} .

Un grafic neorientat este format dintr-un set finit de vârfuri și un set de perechi neordinate de vârfuri, care se numesc muchii . Prin convenție, în analiza algoritmului, numărul de vârfuri din grafic este notat cu n, iar numărul de muchii este notat cu m . O clică într - un grafic G este un complet subgraf al G . Adică, este un subset K a nodurilor astfel încât fiecare două noduri în K sunt cele doua obiective ale unui avantaj în G . O clică maximă este o clică la care nu se mai pot adăuga vârfuri. Pentru fiecare vârf v care nu face parte dintr-o clică maximă, trebuie să existe un alt vârf w care se află în clică și care nu este adiacent v , împiedicând adăugarea lui v la clică. O clică maximă este o clică care include cel mai mare număr posibil de vârfuri. Numărul clică w ( G ) este numărul de noduri dintr - o clică de maxim G .

Au fost studiate mai multe probleme strâns legate de găsirea clicelor.

• În problema maximă a clicului, intrarea este un grafic nedirecționat, iar ieșirea este o clic maximă în grafic. Dacă există mai multe clici maxime, una dintre ele poate fi aleasă în mod arbitrar.
• În problema cu pică maximă a clicei, intrarea este un grafic nedirecționat cu greutăți pe vârfurile sale (sau, mai rar, pe margini), iar ieșirea este o clică cu greutatea totală maximă. Problema maximă de clică este cazul special în care toate greutățile sunt egale. Pe lângă problema optimizării sumei de greutăți, au fost studiate și alte probleme mai complicate de optimizare a bicriteriei.
• În problema maximă de listare a clicurilor, intrarea este un grafic nedirecționat, iar ieșirea este o listă a tuturor clicurilor sale maxime. Problema maximă a clicului poate fi rezolvată folosind ca subrutină un algoritm pentru problema maximă de listare a clicurilor, deoarece clicul maxim trebuie inclus în toate clicurile maxime.
• În problema k- clică, intrarea este un grafic nedirecționat și un număr k . Ieșirea este o clică cu k vârfuri, dacă există, sau o valoare specială care indică faptul că nu există k- clică altfel. În unele variante ale acestei probleme, ieșirea ar trebui să listeze toate clichele de dimensiunea k .
• În problema deciziei de clic, intrarea este un grafic nedirecționat și un număr k , iar ieșirea este o valoare booleană : adevărat dacă graficul conține o k -clic și fals în caz contrar.

Primele patru dintre aceste probleme sunt importante în aplicațiile practice. Problema deciziei clici nu are o importanță practică; este formulat în acest fel pentru a aplica teoria completitudinii NP problemelor de găsire a clicelor.

Problema clică și problema setului independent sunt complementare: o clică în G este un set independent în graficul complement al lui G și invers. Prin urmare, multe rezultate de calcul pot fi aplicate la fel de bine la ambele probleme, iar unele lucrări de cercetare nu fac o distincție clară între cele două probleme. Cu toate acestea, cele două probleme au proprietăți diferite atunci când sunt aplicate familiilor restrânse de grafice. De exemplu, problema clică poate fi rezolvată în timp polinomial pentru grafice plane în timp ce problema setului independent rămâne NP-hard pe graficele plane.

Algoritmi

Găsirea unei singure clici maxime

O clică maximă , uneori numită incluziune-maximă, este o clică care nu este inclusă într-o clică mai mare. Prin urmare, fiecare clică este conținută într-o clică maximă. Clice maxime pot fi foarte mici. Un grafic poate conține o clică non-maximă cu mulți vârfuri și o clică separată de dimensiunea 2 care este maximă. În timp ce o clică maximă (adică cea mai mare) este neapărat maximă, inversul nu se menține. Există câteva tipuri de grafice în care fiecare clică maximă este maximă; acestea sunt complementele ale graficelor bine acoperite , în care fiecare set independent maximă este valoarea maximă. Cu toate acestea, alte grafice au clicuri maxime care nu sunt maxime.

O singură clică maximă poate fi găsită de un algoritm lacom direct . Începând cu o clică arbitrară (de exemplu, orice vârf unic sau chiar setul gol), creșteți clica curentă câte un vârf la un moment dat, parcurgând vârfurile rămase ale graficului. Pentru fiecare vârf v examinat de această buclă, adăugați v la clică dacă este adiacent fiecărui vârf care se află deja în clică și aruncați v altfel. Acest algoritm rulează în timp liniar . Datorită ușurinței de a găsi clici maxime și a dimensiunilor lor potențiale mici, sa acordat o atenție sporită problemei algoritmice mult mai dificile de a găsi o clică maximă sau altfel mare. Cu toate acestea, unele cercetări în algoritmi paraleli au studiat problema găsirii unei clici maxime. În special, problema găsirii primei clicuri lexicografice maxime (cea găsită de algoritmul de mai sus) sa dovedit a fi completă pentru clasa funcțiilor timp polinomial . Acest rezultat implică faptul că este puțin probabil ca problema să fie rezolvabilă în clasa de complexitate paralelă NC .

Clici de dimensiuni fixe

Se poate testa dacă un grafic G conține o clică k- vertex și poate găsi o astfel de clică pe care o conține, utilizând un algoritm de forță brută . Acest algoritm examinează fiecare subgraf cu k vârfuri și verifică dacă formează o clică. Este nevoie de timp O ( n ^k  k ² ) , așa cum este exprimat folosind notația O mare . Acest lucru se datorează faptului că există O ( n ^k ) subgrafe de verificat, fiecare dintre ele având O ( k ² ) muchii a căror prezență în G trebuie verificată. Astfel, problema poate fi rezolvată în timp polinomial ori de câte ori k este o constantă fixă. Cu toate acestea, atunci când k nu are o valoare fixă, dar în schimb poate varia ca parte a intrării în problemă, timpul este exponențial.

Cel mai simplu caz netrivial al problemei de găsire a clicelor este găsirea unui triunghi într-un grafic sau stabilirea echivalentă dacă graficul nu are triunghi . Într-un grafic G cu m muchii, pot exista cel mult Θ ( m ^3/2 ) triunghiuri (folosind notația mare theta pentru a indica faptul că această legătură este strânsă). Cel mai rău caz pentru această formulă apare atunci când G este el însuși o clică. Prin urmare, algoritmii pentru listarea tuturor triunghiurilor trebuie să ia cel puțin Ω ( m ^3/2 ) timp în cel mai rău caz (folosind notația omega mare ) și se cunosc algoritmi care se potrivesc cu acest timp legat. De exemplu, Chiba și Nishizeki (1985) descriu un algoritm care sortează vârfurile în ordine de la cel mai înalt grad la cel mai mic și apoi iterează prin fiecare vârf v din lista sortată, căutând triunghiuri care includ v și nu includ niciun vârf anterior în listă. Pentru a face acest lucru, algoritmul marchează toți vecinii lui v , caută prin toate marginile incidente unui vecin cu v, scoțând un triunghi pentru fiecare margine care are două puncte finale marcate, apoi elimină semnele și șterge v din grafic. După cum arată autorii, timpul pentru acest algoritm este proporțional cu arboricitatea graficului (notat a ( G ) ) înmulțit cu numărul de muchii, care este O ( m  a ( G )) . Deoarece arboricitatea este cel mult O ( m ^1/2 ) , acest algoritm rulează în timp O ( m ^3/2 ) . Mai general, toate clichele k -vertex pot fi listate printr-un algoritm similar care necesită timp proporțional cu numărul de muchii înmulțit cu arboricitatea la putere ( k  - 2) . Pentru graficele cu arboricitate constantă, cum ar fi graficele plane (sau, în general, graficele din orice familie de grafuri minore-închise non-triviale ), acest algoritm ia timp O ( m ) , care este optim, deoarece este liniar în dimensiunea intrării.

Dacă se dorește doar un singur triunghi sau o asigurare că graficul nu prezintă triunghi, sunt posibili algoritmi mai rapizi. După cum observă Itai și Rodeh (1978) , graficul conține un triunghi dacă și numai dacă matricea sa de adiacență și pătratul matricei de adiacență conțin intrări diferite de zero în aceeași celulă. Prin urmare, tehnici de multiplicare rapidă a matricei pot fi aplicate pentru a găsi triunghiuri în timpul O ( n ^2.376 ) . Alon, Yuster și Zwick (1994) au folosit multiplicarea rapidă a matricii pentru a îmbunătăți algoritmul O ( m ^3/2 ) pentru a găsi triunghiuri la O ( m ^1,41 ) . Acești algoritmi bazați pe înmulțirea rapidă a matricii au fost, de asemenea, extinse la probleme de găsire a k- clici pentru valori mai mari ale k .

Listarea tuturor clicurilor maxime

Prin rezultatul Moon & Moser (1965) , fiecare grafic n- vertex are cel mult 3 ^{n / 3} clici maxime. Acestea pot fi enumerate de algoritmul Bron – Kerbosch , o procedură recursivă de backtracking a lui Bron & Kerbosch (1973) . Principalul subrutin recursiv al acestei proceduri are trei argumente: o clică parțial construită (non-maximă), un set de vârfuri candidate care ar putea fi adăugate la clică și un alt set de vârfuri care nu ar trebui adăugate (deoarece acest lucru ar conduce la o clică care a fost deja găsită). Algoritmul încearcă să adauge vârfurile candidate unul câte unul la clica parțială, făcând un apel recursiv pentru fiecare. După ce încercați fiecare dintre aceste vârfuri, îl mută pe setul de vârfuri care nu ar trebui adăugate din nou. Se poate demonstra că variantele acestui algoritm au cel mai rău caz de funcționare O (3 ^{n / 3} ) , care se potrivește cu numărul de clici care ar putea avea nevoie să fie listate. Prin urmare, aceasta oferă o soluție optimă în cel mai rău caz la problema listării tuturor clicurilor maxime. Mai mult, algoritmul Bron – Kerbosch a fost raportat pe scară largă ca fiind mai rapid în practică 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, ar putea fi preferabili alți algoritmi. După cum Tsukiyama și colab. (1977) au arătat că este de asemenea posibil să se enumere toate clicurile maxime într-un grafic într-o perioadă de timp care este polinomială pentru fiecare clic generată. Un algoritm precum al lor în care timpul de funcționare depinde de dimensiunea ieșirii este cunoscut sub numele de algoritm sensibil la ieșire . Algoritmul lor se bazează pe următoarele două observații, care raportează clicurile maxime ale graficului dat G la clicurile maxime ale unui grafic G  \  v format prin eliminarea unui vârf arbitrar v din G :

• Pentru fiecare maxim clica K din G  \  v , fie K continuă să formeze o clică maximă în G sau K  ⋃ { v } formează o clică maximă în G . Prin urmare, G are cel puțin la fel de multe clici maxime ca G  \  v .
• Fiecare clică maximă din G care nu conține v este o clică maximă din G  \  v și fiecare clică maximă din G care conține v poate fi formată dintr-o clică maximă K din G  \  v prin adăugarea v și eliminarea non-vecinilor din v de la K .

Folosind aceste observații pot genera toate clice maxime în G printr-un algoritm recursiv care alege un vârf v în mod arbitrar și apoi, pentru fiecare clică maximă K din G  \  v , scoate atât K cât și clica formată prin adăugarea v la K și eliminarea non -vecinii v . Cu toate acestea, unele clici ale lui G pot fi generate în acest mod din mai multe clici părinte ale lui G  \  v , deci elimină duplicatele prin scoaterea unei clici în G numai atunci când părintele său din G  \  v este lexicografic maxim dintre toate clicele părinte posibile. Pe baza acestui principiu, ele arată că toate clice maxime din G pot fi generate în timpul O ( mn ) per clică, unde m este numărul de muchii din G și n este numărul de vârfuri. Chiba și Nishizeki (1985) îmbunătățesc acest lucru la O ( ma ) pe clică, unde a este arboricitatea graficului dat. Makino & Uno (2004) oferă un algoritm alternativ sensibil la ieșire bazat pe multiplicarea rapidă a matricei. Johnson & Yannakakis (1988) arată că este chiar posibil să enumerăm toate clice maxime în ordine lexicografică cu întârziere polinomială pe clică. Cu toate acestea, alegerea ordonării este importantă pentru eficiența acestui algoritm: pentru inversul acestei ordine, nu există un algoritm de întârziere polinomială, cu excepția cazului în care P = NP .

Pe baza acestui rezultat, este posibil să se enumere toate clice maxime în timp polinomial, pentru familii de grafice în care numărul de clici este delimitat polinomial. Aceste familii includ grafice corzii , grafice complet , graficele triunghi liber , graficele interval , graficele de mărginite boxicity și graficele planare . În special, graficele plane au O ( n ) clici, de dimensiuni cel mult constante, care pot fi listate în timp liniar. Același lucru este valabil pentru orice familie de grafice care este atât rar (având un număr de muchii, cel mult o dată constantă a numărului de vârfuri), cât și închisă sub operația de a lua subgrafe.

Găsirea unor clici maxime în grafice arbitrare

Este posibil să găsiți clica maximă sau numărul de clică, al unui grafic arbitrar n- vertex în timp O (3 ^{n / 3} ) = O (1,4422 ⁿ ) utilizând unul dintre algoritmii descriși mai sus pentru a enumera toate clice maxime în graficul și returnarea celui mai mare. Cu toate acestea, pentru această variantă a problemei de clică sunt mai bune limite de timp în cel mai rău caz. Algoritmul lui Tarjan și Trojanowski (1977) rezolvă această problemă în timp O (2 ^{n / 3} ) = O (1,2599 ⁿ ) . Este o schemă de urmărire recursivă similară cu cea a algoritmului Bron – Kerbosch , dar este capabilă să elimine unele apeluri recursive atunci când se poate arăta că clicurile găsite în cadrul apelului vor fi suboptimale. Jian (1986) a îmbunătățit timpul până la O (2 ^{0,304 n} ) = O (1,2346 ⁿ ) , iar Robson (1986) l-a îmbunătățit la O (2 ^{0,276 n} ) = O (1,2108 ⁿ ) , în detrimentul unei utilizări mai mari a spațiului . Algoritmul lui Robson combină o schemă similară de backtracking (cu o analiză de caz mai complicată) și o tehnică de programare dinamică în care soluția optimă este precomputată pentru toate subgrafele mici conectate ale graficului complementului . Aceste soluții parțiale sunt utilizate pentru scurtarea recursivității de urmărire înapoi. Cel mai rapid algoritm cunoscut astăzi este o versiune rafinată a acestei metode de Robson (2001) care rulează în timp O (2 ^{0,249 n} ) = O (1,1888 ⁿ ) .

De asemenea, s-au efectuat cercetări ample asupra algoritmilor euristici pentru rezolvarea problemelor maxime de clică fără garanții de rulare în cel mai rău caz, bazate pe metode care includ ramuri și legături , căutare locală , algoritmi lacomi și programare de constrângeri . Metodologiile de calcul non-standard care au fost sugerate pentru găsirea unor clici includ calculul ADN și calculul cuantic adiabatic . Problema maximă de clică a făcut obiectul unei provocări de implementare sponsorizate de DIMACS în 1992-1993 și a unei colecții de grafice utilizate ca etaloane pentru provocare, care este disponibilă publicului.

Clase speciale de grafice

În acest grafic de permutare , clicurile maxime corespund celor mai lungi subsecvențe descrescătoare (4,3,1) și (4,3,2) ale permutării definitorii.

Graficele plane și alte familii de grafice rare au fost discutate mai sus: au liniar multe clici maxime, de mărime mărginită, care pot fi listate în timp liniar. În special, pentru graficele plane, orice clică poate avea cel mult patru vârfuri, conform teoremei lui Kuratowski .

Graficele perfecte sunt definite de proprietățile că numărul lor de clică este egal cu numărul lor cromatic și că această egalitate este valabilă și în fiecare dintre subgrafele lor induse . Pentru grafice perfecte, este posibil să se găsească o clică maximă în timp polinomial, folosind un algoritm bazat pe programare semidefinită . Cu toate acestea, această metodă este complexă și necombinatorie, iar algoritmi specializați de găsire a clicurilor au fost dezvoltați pentru multe subclase de grafice perfecte. În graficele complementare ale graficelor bipartite , teorema lui Kőnig permite rezolvarea problemei maxime a clicii folosind tehnici de potrivire . Într-o altă clasă de grafice perfecte, graficele de permutare , o clică maximă este cea mai lungă subsecvență descrescătoare a permutației care definește graficul și poate fi găsită folosind algoritmi cunoscuți pentru cea mai lungă problemă de subsecvență descrescătoare. Dimpotrivă, fiecare situație a celei mai lungi probleme de subsecvență descrescătoare poate fi descrisă echivalent ca o problemă a găsirii unei clici maxime într-un grafic de permutare. Chiar și Pnueli și Lempel (1972) oferă un algoritm alternativ în timp pătratic pentru clici maxime în graficele de comparabilitate , o clasă mai largă de grafice perfecte care include graficele de permutare ca un caz special. În graficele acordurilor , clico-urile maxime pot fi găsite prin listarea vârfurilor într-o ordonare de eliminare și verificarea vecinătăților de clică a fiecărui vârf în această ordonare.

În unele cazuri, acești algoritmi pot fi extinși și la alte clase de grafice, care nu sunt perfecte. De exemplu, într-un grafic de cerc , vecinătatea fiecărui vârf este un grafic de permutare, deci o clică maximă într-un grafic de cerc poate fi găsită prin aplicarea algoritmului graficului de permutare la fiecare vecinătate. În mod similar, într-un grafic de disc unitate (cu o reprezentare geometrică cunoscută), există un algoritm de timp polinomial pentru clicuri maxime bazat pe aplicarea algoritmului pentru complementele de grafice bipartite la vecinătățile comune de perechi de vârfuri.

Problema algoritmică a găsirii unei clici maxime într-un grafic aleatoriu extras din modelul Erdős – Rényi (în care fiecare margine apare cu probabilitate 1/2 , independent de celelalte margini) a fost sugerată de Karp (1976) . Deoarece clica maximă într-un grafic aleatoriu are dimensiuni logaritmice cu probabilitate mare, poate fi găsită printr-o căutare a forței brute în timpul așteptat 2 ^{O (log 2 n )} . Acesta este un timp cvasi-polinomial . Deși numărul de clici ale unor astfel de grafice este de obicei foarte apropiat de 2 log ₂ n , algoritmi simpli lacomi , precum și tehnici de aproximare randomizate mai sofisticate găsesc doar clici cu dimensiunea log ₂ n , pe jumătate la fel de mare. Numărul de clici maxime din astfel de grafice este cu exponențială de probabilitate mare în log ² n , ceea ce împiedică metodele care listează toate clice maxime să ruleze în timp polinomial. Datorită dificultății acestei probleme, mai mulți autori au investigat problema clicelor plantate , problema clicii pe grafice aleatorii care au fost mărite prin adăugarea unor clici mari. În timp ce metodele spectrale și programarea semidefinită pot detecta clici ascunse de dimensiunea Ω ( √ n ) , nu sunt cunoscuți în prezent algoritmi de timp polinomial pentru a detecta cei de dimensiunea o ( √ n ) (exprimată utilizând notația little-o ).

Algoritmi de aproximare

Mai mulți autori au luat în considerare algoritmi de aproximare care încearcă să găsească o clică sau un set independent care, deși nu este maxim, are o dimensiune cât mai apropiată de cea maximă care poate fi găsită în timp polinomial. Deși o mare parte a acestei lucrări s-a concentrat pe seturi independente în grafice rare, caz care nu are sens pentru problema complementară a clicii, s-a lucrat și la algoritmi de aproximare care nu utilizează astfel de ipoteze de raritate.

Feige (2004) descrie un algoritm de timp polinomial care găsește o clică de dimensiunea Ω ((log  n / log log  n ) ² ) în orice grafic care are numărul cliquei Ω ( n / log ^k n ) pentru orice constantă k . Prin utilizarea acestui algoritm atunci când numărul de clic al unui grafic de intrare dat este între n / log  n și n / log ³ n , trecerea la un algoritm diferit al lui Boppana și Halldórsson (1992) pentru grafice cu numere de clic mai mari și alegerea unui clica vertexului dacă ambii algoritmi nu reușesc să găsească ceva, Feige oferă un algoritm de aproximare care găsește o clică cu un număr de vârfuri într-un factor de O ( n (log log  n ) ² / log ³ n ) din maxim. Deși raportul de aproximare al acestui algoritm este slab, acesta este cel mai cunoscut până în prezent. Rezultatele privind duritatea de aproximare descrise mai jos sugerează că nu poate exista un algoritm de aproximare cu un raport de aproximare semnificativ mai mic decât liniar.

Limite inferioare

NP-completitudine

Instanța de satisfacție 3-CNF (x ∨ x ∨ y) ∧ (~ x ∨ ~ y ∨ ~ y) ∧ (~ x ∨ y ∨ y) redusă la Clique. Vârfurile verzi formează o 3-clică și corespund unei sarcini satisfăcătoare.

Problema deciziei de clică este complet NP . A fost una dintre cele 21 de probleme originale ale lui Richard Karp prezentate NP-complete în lucrarea sa din 1972 „Reducibility Among Combinatorial Problems”. Această problemă a fost menționată și în lucrarea lui Stephen Cook care introduce teoria problemelor NP-complete. Din cauza durității problemei deciziei, problema găsirii unei clici maxime este, de asemenea, NP-hard. Dacă s-ar putea rezolva, s-ar putea rezolva și problema deciziei, comparând dimensiunea clicii maxime cu parametrul de dimensiune dat ca intrare în problema deciziei.

Dovada de completitudine NP a lui Karp este o reducere mult-una față de problema de satisfacție booleană . Descrie cum se pot traduce formulele booleene în formă normală conjunctivă (CNF) în instanțe echivalente cu problema maximă a clicii. La rândul său, satisfacția a fost dovedită NP-completă în teorema Cook-Levin . Dintr-o anumită formulă CNF, Karp formează un grafic care are un vârf pentru fiecare pereche ( v , c ) , unde v este o variabilă sau negația sa și c este o clauză din formula care conține v . Două dintre aceste vârfuri sunt conectate printr-o margine dacă reprezintă alocări de variabile compatibile pentru clauze diferite. Adică, există o margine de la ( v , c ) la ( u , d ) ori de câte ori c  ≠  d și u și v nu sunt negațiile celuilalt. Dacă k denotă numărul de clauze din formula CNF, atunci clicurile k -vertex din acest grafic reprezintă moduri consistente de atribuire a unor valori de adevăr unora dintre variabilele sale pentru a satisface formula. Prin urmare, formula este satisfăcătoare dacă și numai dacă există o clică k- vertex.

Unele probleme NP-complete (cum ar fi problema vânzătorului călător în graficele plane ) pot fi rezolvate în timp care este exponențial într-o funcție subliniară a parametrului dimensiunii de intrare n , semnificativ mai rapid decât o căutare cu forță brută. Cu toate acestea, este puțin probabil ca o astfel de legătură de timp subexponențială să fie posibilă pentru problema clică în grafice arbitrare, deoarece ar implica limite în mod similar subexponențiale pentru multe alte probleme standard NP-complete.

Complexitatea circuitului

Un circuit monoton pentru a detecta o k- clică într-un grafic n- vertex pentru k  = 3 și n  = 4 . Fiecare intrare în circuit codifică prezența sau absența unei anumite muchii (roșii) în grafic. Circuitul folosește o poartă internă și o poartă pentru a detecta fiecare k- clică potențială .

Dificultatea de calcul a problemei clice a condus-o să fie folosită pentru a dovedi mai multe limite inferioare ale complexității circuitului . Existența unei clici de o anumită dimensiune este o proprietate de grafic monotonă , ceea ce înseamnă că, dacă o clică există într-un grafic dat, aceasta va exista în orice supergraf . Deoarece această proprietate este monotonă, trebuie să existe un circuit monoton, care utilizează numai și porți și sau porți , pentru a rezolva problema deciziei clicii pentru o anumită dimensiune clică fixă. Cu toate acestea, dimensiunea acestor circuite se poate dovedi a fi o funcție super-polinomială a numărului de vârfuri și a dimensiunii clici, exponențială în rădăcina cubică a numărului de vârfuri. Chiar dacă este permis un număr mic de porți NU , complexitatea rămâne superpolinomială. În plus, adâncimea unui circuit monoton pentru problema clicii utilizând porți de ventilare limitată trebuie să fie cel puțin un polinom în dimensiunea clicii.

Complexitatea arborelui decizional

Un arbore de decizie simplu pentru a detecta prezența unei 3-clici într-un grafic cu 4 vârfuri. Folosește până la 6 întrebări de forma „Există muchia roșie?”, Care se potrivește cu legătura optimă n ( n  - 1) / 2.

Complexitatea (deterministă) a arborelui decizional al determinării unei proprietăți grafice este numărul de întrebări de forma „Există o margine între vârful u și vârful v ?” la care trebuie răspuns în cel mai rău caz pentru a determina dacă un grafic are o anumită proprietate. Adică, este înălțimea minimă a unui arbore de decizie boolean pentru problemă. Există n ( n  - 1) / 2 posibile întrebări de pus. Prin urmare, orice proprietate a graficului poate fi determinată cu cel mult n ( n  - 1) / 2 întrebări. Este, de asemenea, posibil să se definească complexitatea arborelui decizional aleator și cuantic al unei proprietăți, numărul așteptat de întrebări (pentru cel mai rău caz de intrare) la care trebuie răspuns un algoritm aleatoriu sau cuantic pentru a determina corect dacă graficul dat are proprietatea .

Deoarece proprietatea de a conține o clică este monotonă, ea este acoperită de conjectura Aanderaa – Karp – Rosenberg , care afirmă că complexitatea deterministică a arborelui decizional al determinării oricărei proprietăți de graf monoton non-banale este exact n ( n  - 1) / 2 . Pentru proprietăți grafice monotone arbitrare, această conjectură rămâne nedovedită. Cu toate acestea, pentru arborii de decizie deterministici și pentru orice k din intervalul 2 ≤ k ≤ n , proprietatea de a conține o k -clică s-a arătat că are complexitatea arborelui decizional exact n ( n  - 1) / 2 de Bollobás (1976) . Arborii de decizie deterministă necesită, de asemenea, dimensiuni exponențiale pentru a detecta clici, sau dimensiuni mari de polinom pentru a detecta clici de dimensiuni mărginite.

Conjectura Aanderaa – Karp – Rosenberg afirmă, de asemenea, că complexitatea randomizată a arborelui decizional al funcțiilor monotone non-triviale este Θ ( n ² ) . Conjectura rămâne din nou nedovedită, dar a fost rezolvată pentru proprietatea de a conține o k clică pentru 2 ≤ k ≤ n . Se știe că această proprietate are complexitatea randomizată a arborelui decizional Θ ( n ² ) . Pentru arborii de decizie cuantici, cea mai cunoscută limită inferioară este Ω ( n ) , dar nu se cunoaște niciun algoritm de potrivire pentru cazul k ≥ 3 .

Intractabilitatea parametrilor fixi

Complexitatea parametrizată este studiul teoretic al complexității problemelor care sunt în mod natural echipate cu un parametru întreg mic k și pentru care problema devine mai dificilă pe măsură ce k crește, cum ar fi găsirea k -cliques în grafice. Se spune că o problemă poate fi tratată cu parametri fixi dacă există un algoritm pentru rezolvarea acesteia pe intrări de dimensiunea n și o funcție f , astfel încât algoritmul să ruleze în timpul f ( k )  n ^{O (1)} . Adică, este tratabil cu parametru fix dacă poate fi rezolvat în timp polinomial pentru orice valoare fixă ​​a lui k și, în plus, dacă exponentul polinomului nu depinde de k .

Pentru găsirea unor clici k -vertex, algoritmul de căutare a forței brute are timp de funcționare O ( n ^k k ² ) . Deoarece exponentul lui n depinde de k , acest algoritm nu este tratabil cu parametri fixi. Deși poate fi îmbunătățit prin multiplicarea rapidă a matricei, timpul de rulare are încă un exponent liniar în k Astfel, deși timpul de rulare al algoritmilor cunoscuți pentru problema clică este polinomial pentru orice k fix , acești algoritmi nu sunt suficienți pentru parametrul fix tractabilitate. Downey & Fellows (1995) au definit o ierarhie a problemelor parametrizate, ierarhia W, pe care o presupuneau că nu au algoritmi tratabili cu parametri fixi. Au dovedit că setul independent (sau, în mod echivalent, clica) este greu pentru primul nivel al acestei ierarhii, W [1] . Astfel, conform conjecturii lor, clica nu are algoritm tratabil cu parametri fixi. Mai mult, acest rezultat oferă baza pentru dovezile durității W [1] a multor alte probleme și, astfel, servește ca un analog al teoremei Cook-Levin pentru complexitatea parametrizată.

Chen și colab. (2006) au arătat că găsirea unor clici k -vertex nu poate fi făcută în timpul n ^{o ( k )} decât dacă ipoteza exponențială a timpului eșuează. Din nou, aceasta oferă dovezi că nu este posibil nici un algoritm tratabil cu parametri fixi.

Deși problemele de listare a clicurilor maxime sau de găsire a clicurilor maxime sunt puțin probabil să fie tratabile cu parametri fixi cu parametrul k , ele pot fi tratate cu parametri fixi pentru alți parametri de complexitate a instanței. De exemplu, se știe că ambele probleme pot fi tratate cu parametri fixi când sunt parametrizate de degenerarea graficului de intrare.

Duritatea aproximării

Un grafic al relațiilor de compatibilitate între eșantioane pe 2 biți de șiruri de probă pe 3 biți. Fiecare clică maximă (triunghi) din acest grafic reprezintă toate modurile de eșantionare a unui singur șir de 3 biți. Dovada inaproximării problemei clică implică subgrafe induse de grafuri definite în mod analog pentru un număr mai mare de biți.

Rezultatele slabe care sugerează că problema clicii ar putea fi greu de aproximat sunt cunoscute de mult timp. Garey & Johnson (1978) au observat că, deoarece numărul clica preia valori întregi mici și este NP greu de calculat, nu poate avea o schemă de aproximare complet polinomială . Dacă ar fi disponibilă o aproximare prea precisă, rotunjirea valorii sale la un număr întreg ar da numărul exact al clicii. Cu toate acestea, s-au știut puțin mai mult până la începutul anilor 1990, când mai mulți autori au început să facă legături între aproximarea clicelor maxime și dovezile verificabile probabilistic . Ei au folosit aceste conexiuni pentru a dovedi duritatea rezultatelor de aproximare pentru problema maximă a clicăi. După multe îmbunătățiri ale acestor rezultate, se știe acum că, pentru fiecare număr real ε  > 0 , nu poate exista un algoritm de timp polinomial care să aproxime clica maximă într-un factor mai bun decât O ( n ^{1 -  ε} ) , cu excepția cazului în care P = NP .

Ideea brută a acestor rezultate de inapproximabilitate este de a forma un grafic care reprezintă un sistem de probă probabilist verificabil pentru o problemă NP-completă, cum ar fi problema de satisfacție booleană. Într-un sistem de probă verificabil probabilistic, o dovadă este reprezentată ca o succesiune de biți. O situație a problemei satisfacției ar trebui să aibă o dovadă validă dacă și numai dacă este satisfăcătoare. Dovada este verificată de un algoritm care, după un calcul în timp polinomial la intrarea în problema de satisfacție, alege să examineze un număr mic de poziții alese aleatoriu ale șirului de dovadă. În funcție de valorile care se găsesc la acel eșantion de biți, verificatorul va accepta sau respinge dovada, fără a privi restul de biți. Falsele negative nu sunt permise: trebuie întotdeauna acceptată o dovadă validă. Cu toate acestea, o dovadă nevalidă poate fi uneori acceptată din greșeală. Pentru fiecare dovadă nevalidă, probabilitatea ca verificatorul să o accepte trebuie să fie mică.

Pentru a transforma un sistem de probă verificabil probabilistic de acest tip într-o problemă de clică, se formează un grafic cu un vârf pentru fiecare posibilă acceptare a testului de verificare. Adică, un vârf este definit de una dintre posibilele alegeri aleatorii de seturi de poziții de examinat și de valorile de biți pentru acele poziții care ar determina verificatorul să accepte dovada. Poate fi reprezentat de un cuvânt parțial cu 0 sau 1 la fiecare poziție examinată și un caracter wildcard la fiecare poziție rămasă. Două vârfuri sunt adiacente, în acest grafic, dacă cele două curse de acceptare corespunzătoare văd aceleași valori de biți la fiecare poziție pe care o examinează amândoi. Fiecare șir de dovadă (valid sau nevalid) corespunde unei clici, setului de rulări de acceptare care văd acel șir de probă și toate clice maxime apar în acest fel. Una dintre aceste clici este mare dacă și numai dacă corespunde unui șir de probe acceptat de mulți verificatori de probă. Dacă instanța de satisfacție originală este satisfăcătoare, va avea un șir de dovadă valid, unul care este acceptat de toate rulările de verificare, iar acest șir va corespunde unei clici mari din grafic. Cu toate acestea, dacă instanța inițială nu este satisfăcătoare, atunci toate șirurile de probă sunt nevalide, fiecare șir de probă are doar un număr mic de rulări de verificare care o acceptă din greșeală și toate clicurile sunt mici. Prin urmare, dacă s-ar putea distinge în timp polinomial graficele care au clici mari și grafice în care toate clicele sunt mici sau dacă s-ar putea aproxima cu exactitate problema clicii, atunci aplicarea acestei aproximări la graficele generate de instanțe de satisfacție ar permite instanțe satisfăcătoare să să fie distins de instanțele nesatisfăcătoare. Cu toate acestea, acest lucru nu este posibil decât dacă P = NP.

Note

Referințe

Sondaje și manuale

Presa populară

Articole de cercetare