Problema fisurii

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Algoritmul forței brute găsește o crăpătură de 4 în acest grafic cu 7 vârfuri (complementul graficului de cale cu 7 vârfuri) prin verificarea sistematică a tuturor subgrafelor cu 4 vârfuri C (7,4) = 35 pentru completare.

În informatică , problema fisurilor se referă la oricare dintre problemele legate de găsirea anumitor subgrafe complete („ fisuri ”) într-un grafic , adică seturi de elemente unde fiecare pereche de elemente este conectată.

De exemplu, problema maximă de clică apare în următorul scenariu din lumea reală. Luați în considerare o rețea socială , în care vârfurile graficului reprezintă oameni, iar marginile grafului reprezintă reciproc cunoștințele. Pentru a găsi un subset mai mare de oameni care se cunosc toți, se poate inspecta sistematic toate subseturile, un proces care consumă prea mult timp pentru a fi practic pentru rețelele sociale care includ mai mult de câteva zeci de oameni. Deși această căutare cu forță brută poate fi îmbunătățită prin algoritmi mai eficienți, toți acești algoritmi necesită timp exponențial pentru a rezolva problema. Astfel, o mare parte din teoria problemei clica 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. [1] Împreună cu aplicațiile sale în rețelele de socializare, problema clică are, de asemenea, multe aplicații în bioinformatică și chimie computațională . [2]

Problemele clice includ:

  • găsiți clica maximă (o clică cu cel mai mare număr de vârfuri),
  • găsiți o clică cu greutatea maximă într-un grafic ponderat ,
  • enumerați toate fisurile maxime (fisuri care nu pot fi extinse),
  • rezolvați problema deciziei de a verifica dacă un grafic conține o fisură mai mare decât o dimensiune dată.

Toate aceste probleme sunt dificile: problema deciziei de crack este NP-completă (una dintre cele 21 de probleme Karp-NP-complete ), problema găsirii fisurii maxime este atât intratabilă cu un parametru fix , cât și dificil de aproximat și listează toate valorile maxime fisurile pot lua timp exponențial deoarece există grafice cu un număr exponențial de fisuri maxime. Cu toate acestea, există algoritmi pentru aceste probleme care rulează în timp exponențial sau care gestionează anumite grafice de intrare în timp polinomiale mai specializate. [1]

Istorie

Deși subgrafele complete sunt concepute pentru mai mult timp în matematică, [3] termenul „bandă” (clica în engleza originală) și problema listării algoritmice a clicurilor sunt ambele din științele sociale, unde subgrafele complete sunt folosite pentru a modela clici sociale, grupuri de oameni care se cunosc toți. Terminologia „clicii” provine de la Luce & Perry (1949) , iar primul algoritm care rezolvă problema clicii este cel al lui Harari & Ross (1957) , [1] care au fost motivați de aplicația sociologică.

De la lucrările lui Harary și Ross, mulți alții au conceput algoritmi pentru diferite versiuni ale problemei clici. [1] În anii 1970, cercetătorii au început să studieze acești algoritmi din punctul de vedere al analizei în cel mai rău caz ; vezi, de exemplu, Tarjan și Trojanowski (1977) , o lucrare timpurie despre complexitatea celui mai rău caz în problema maximă a clicii. Tot în anii 1970, începând cu lucrările lui Cook (1971) și Karp (1972) , cercetătorii au început să găsească justificări matematice pentru dificultatea percepută a problemei clici în teoria completitudinii NP și a rezultatelor legate de intractabilitate. În anii 1990, o serie de studii inovatoare au început cu Feige și colab. (1991) și raportat la vremea respectivă de către ziarele de vârf [4], a arătat că nu este posibil nici măcar să aproximăm problema cu precizie și eficiență.

Definiții

Pictogramă lupă mgx2.svg Același subiect în detaliu: Clique (teoria graficelor) .
Graficul prezentat are o singură clică maximă, triunghiul {1,2,5} și alte patru clici maxime, perechile {2,3}, {3,4}, {4,5} și {4,6} .

Un grafic indirect 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 fisură într-un grafic G este un subgraf complet al lui G ; adică este un subset S de vârfuri astfel încât fiecare doi vârfuri din S sunt conectate printr-o margine din G. O fisură maximă este o fisură la care nu se pot adăuga alte vârfuri; o fisură maximă este o fisură care include cel mai mare număr posibil de vârfuri, iar numărul fisurii ω ( G ) este numărul de vârfuri într-o fisură maximă de G. [1]

Au fost studiate mai multe probleme strâns legate de cercetarea fisurilor.

  • În problema maximă a clicului, intrarea este un grafic indirect, iar ieșirea este o clic maximă a graficului. Dacă există mai multe fisuri maxime, doar una trebuie să fie ieșirea.
  • În problema maximă a fisurii ponderate, intrarea este un grafic indirect cu greutățile pe vârfurile sale (sau, mai rar, pe margini), iar ieșirea este o fisură cu greutatea totală maximă. Problema maximă a fisurării este cazul special în care greutățile sunt la fel.
  • În problema de listare a clicurilor maxime, intrarea este un grafic indirect, iar ieșirea este o listă a tuturor clicurilor maxime. Problema maximă de fisurare poate fi rezolvată folosind un algoritm pentru problema maximă de listare a fisurilor ca subrutină, deoarece fisura maximă trebuie inclusă între toate fisurile maxime.
  • În problema k- crack, intrarea este un grafic indirect și un număr k , iar ieșirea este o fisură de dimensiune k dacă există una (sau, uneori, toate fisurile dimensiunii k ).
  • În problema deciziei de clic, intrarea este un grafic indirect și un număr k , iar ieșirea este o valoare booleană : adevărat dacă graficul conține un crack k , și fals în caz contrar.

Primele patru dintre aceste probleme sunt importante în aplicațiile practice; problema deciziei crack nu este, dar este necesar să se aplice teoria completitudinii NP problemelor de căutare crack.

Problema clică și problema setului independent sunt complementare: o clică în G este o mulțime din 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 disting 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 fisurii poate fi rezolvată în timp polinomial pentru graficele plane , [5] în timp ce problema setului independent rămâne dificil de NP pe graficele plane.

Algoritmi

Maxim versus maxim

O fisură maximă , uneori numită maximă cu includere, este o fisură care nu este inclusă într-o fisură mai mare. De aceea, rețineți că fiecare fisură este conținută într-o fisură maximă.

Fisurile maxime pot fi foarte mici. Un grafic poate conține o clică non-maximă cu mulți vârfuri și o clică bidimensională separată care este maximă. În timp ce o fisură maximă (adică mai mare) este neapărat maximă, inversul nu se menține. Există câteva tipuri de grafice în care fiecare fisură este maximă ( complementele graficelor bine acoperite , care includ în special grafice complete , grafice fără triunghiuri fără vârfuri izolate , grafuri multiple multipartite și k- arbori ), dar alte grafice au maxim clipuri care nu sunt maxime.

Găsirea unei fisuri maxime este imediată: pornind de la o clică arbitrară (de exemplu, un singur vârf), clica curentă este crescută câte un vârf la un moment dat, iterând peste vârfurile rămase ale graficului, adăugând un vârf dacă este conectat la fiecare vârful fisurii actuale și aruncându-l altfel. Acest algoritm funcționează în timp liniar . Datorită ușurinței de a găsi fisuri maxime și a dimensiunii potențiale a acestora, s-a acordat mai multă atenție problemei algoritmice mult mai dificile de a găsi o fisură maximă sau altfel mare decât a fost dată problemei de a găsi o fisură maximă unică.

S-au remediat fisurile de dimensiune

Un algoritm de forță brută pentru a testa dacă un grafic G conține un cli cu k vârfuri și pentru a găsi orice astfel de fisură pe care o conține, trebuie să examineze fiecare subgraf cu cel puțin k vârfuri și să verifice dacă formează o fisură. Acest algoritm folosește timpul O ( n k k 2 ): există subgrafe O ( n k ) de verificat, fiecare dintre ele având margini O ( k 2 ) a căror prezență în G trebuie verificată. Prin urmare, problema poate fi rezolvată în timp polinomial ori de câte ori k este o constantă fixă. Cu toate acestea, atunci când k face parte din introducerea problemei, timpul este exponențial. [6]

Cel mai simplu caz netrivial al problemei găsirii unei clici este găsirea unui triunghi într-un grafic sau echivalent pentru a determina dacă graficul este fără triunghiuri . Într-un grafic cu m muchii, pot exista cel mult Θ ( m 3/2 ) triunghiuri; cel mai rău caz apare atunci când G este el însuși o fisură. Prin urmare, algoritmii pentru listarea tuturor triunghiurilor trebuie să ia cel puțin timpul Ω ( m 3/2 ) în cel mai rău caz, iar algoritmii sunt cunoscuți pentru a se potrivi cu această limită de timp. [7] De exemplu, Chiba și Nishizeki (1985) descriu un algoritm care sortează vârfurile de la cel mai înalt la cel mai mic grad și apoi iterează prin fiecare vârf v din lista sortată, căutând triunghiuri care includ v și care nu includ niciun vârf anterior. a listei. Pentru a face acest lucru, algoritmul marchează toți vecinii lui v , caută prin toate marginile incidente unui vecin cu v, producând ca ieșire un triunghi pentru fiecare margine care are marcate două puncte extreme, apoi elimină marcajele și șterge v de la graficul. După cum arată autorii, timpul pentru acest algoritm este proporțional cu arboricitatea graficului ( a ( G )) prin numărul de muchii, care este O ( m a ( G )). Deoarece arboricitatea este cel mult O ( m 1/2 ), acest algoritm funcționează în timp O ( m 3/2 ). Mai general, toate fisurile cu k vârfuri pot fi listate printr-un algoritm similar care durează un timp proporțional cu numărul de muchii pentru puterea ( k - 2) a arboricității. [5] Pentru graficele de arboricitate constantă, cum ar fi graficele plane (sau, în general, graficele oricărei familii de grafice minore închise netriviale), acest algoritm folosește timpul O ( m ), care este optim, deoarece este liniar în dimensiunea intrarea.

Dacă doriți doar un singur triunghi sau asigurarea că graficul este fără triunghiuri, 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 rapide de multiplicare a matricii, cum ar fi algoritmul Coppersmith-Winograd, pot fi aplicate pentru a găsi triunghiuri în timpul O ( n 2.376 ), care poate fi mai rapid decât O ( m 3/2 ) pentru grafice suficient de dense . Alon, Yuster & Zwick (1994) au îmbunătățit algoritmul O ( m 3/2 ) pentru a găsi triunghiuri O ( m 1,41 ) folosind multiplicarea rapidă a matricei. Această idee a utilizării înmulțirii rapide a matricii pentru a găsi triunghiuri a fost, de asemenea, extinsă la problemele de a găsi k- fisuri pentru valori mai mari ale lui k . [8]

Enumerați toate fisurile maxime

Conform unui rezultat al lui Moon & Moser (1965) , orice grafic cu n vârfuri are cel mult 3 n / 3 fisuri maxime. Algoritmul L- Bron-Kerbosch este o procedură recursivă care revine înapoi (backtracking) a lui Bron & Kerbosch (1973) care mărește un candidat de clică având în vedere un vârf la un moment dat, sau adăugându-l la clicul candidat sau un set de vârfuri care nu sunt excluse pot fi în clică, dar trebuie să aibă unii non-vecini în clica finală; se poate arăta că variantele acestui algoritm au cel mai rău timp de execuție O (3 n / 3 ). [9] Astfel, aceasta oferă o soluție optimă, în cel mai rău caz, la problema listării tuturor seturilor maxime independente; în plus, s-a raportat pe scară largă că algoritmul Bron-Kerbosch este în practică mai rapid decât alternativele sale. [10]

După cum au arătat Tsukiyama, Ide, Ariyoshi și Shirakawa (1977) , este, de asemenea, posibil să se enumere toate clice maxime într-un grafic într-un timp care este polinomial pentru fiecare clică generată. Un algoritm ca al lor în care timpul de execuție depinde de mărimea ieșirii este cunoscut sub numele de algoritm sensibil la ieșire . Algoritmul lor se bazează pe următoarele două observații, care conectează fisurile maxime ale graficului dat G la fisurile maxime ale unui grafic G \ v format prin eliminarea unui vârf arbitrar v din G :

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

Folosind aceste observații pot genera toate fisurile maxime din G prin intermediul unui algoritm recursiv care, pentru fiecare fisură maximă C din G \ v , produce ca ieșire C și fisura formată prin adăugarea v la C și eliminarea tuturor non-vecinilor lui v . Cu toate acestea, unele fisuri din G pot fi generate în acest fel de mai multe clici părinte ale lui G \ v , astfel încât elimină duplicatele producând ca ieșire o fisură în G numai atunci când părintele său din G \ v este lexicografic maxim dintre toate fisurile posibile părinţi. Pe baza acestui principiu, ele arată că toate fisurile maxime din G pot fi generate în timpul O ( mn ) pentru fiecare fisură, unde m este numărul de muchii din G și n este numărul de vârfuri; Chiba și Nishizeki (1985) îmbunătățesc această valoare la O ( ma ) pentru fiecare clică, unde a este arboricitatea graficului dat. Makino & Uno (2004) furnizează un algoritm alternativ sensibil la ieșire bazat pe multiplicarea rapidă a matricei, iar Johnson & Yannakakis (1988) arată că este, de asemenea, posibil să se enumere toate fisurile maxime în ordine lexicografică cu o întârziere polinomială pentru fiecare fisură, deși inversul acestui ordin este NP-dificil de generat.

Pe baza acestui rezultat, este posibilă listarea tuturor fisurilor maxime în timp polinomial, pentru familiile de grafice în care numărul fisurilor este limitat polinomial. Aceste familii includ grafice corzii , complet grafice, non-triunghiulare grafice, interval grafice, limitate bossicity grafice și graficele planare . [11] În special, graficele plane și, mai general, orice familie de grafice care sunt ambele rare (având ca număr de muchii cel mult o constantă pentru numărul de vârfuri), sunt închise pe baza operației de preluare a subgrafelor, are O ( n ) fisuri, cel mult de dimensiuni constante, care pot fi listate în timp liniar. [5] [12]

Găsirea fisurilor maxime în grafice arbitrare

Este posibil să se găsească fisura maximă, sau numărul fisurii, al unui grafic arbitrar n- vârf în timp O (3 n / 3 ) = O (1,4422 n ) folosind unul dintre algoritmii descriși mai sus pentru a enumera toate fisurile maxime ale graficul și returnează-l pe cel mai mare. Cu toate acestea, pentru această variantă a problemei fisurilor, sunt posibile termene mai bune în cel mai rău caz. Algoritmul lui Tarjan și Trojanowski (1977) rezolvă această problemă în timp O (2 n / 3 ) = O (1,2599 n ); este un sistem de backtracking recursiv similară cu cea a algoritmului Bron-Kerbosch , dar este capabil de a elimina unele apeluri recursive , atunci când se poate demonstra că este garantat că o altă combinație de noduri care nu sunt utilizate în derivațiile de apel la o soluție care este la cel puțin la fel de bine. Jian (1986) a îmbunătățit acest lucru în O (2 0,304 n ) = O (1,2346 n ). Robson (1986) a îmbunătățit-o în timp O (2 0,276 n ) = O (1,2108 n ), în detrimentul unei utilizări mai mari a spațiului, prin intermediul unui model similar înapoi cu o analiză de caz mai complicată, împreună cu o tehnică de programare dinamică în care soluția optimă este precomputată pentru toate subgrafele mici conectate ale graficului complementului și aceste soluții parțiale sunt utilizate pentru a scurta traversarea înapoi. Cel mai rapid algoritm cunoscut astăzi este cel datorat lui Robson (2001) , care rulează în timp O (2 0,249 n ) = O (1,1888 n ).

Au existat, de asemenea, cercetări ample privind algoritmii euristici pentru a rezolva problemele maxime de fisurare fără garanții în timpii de execuție în cel mai rău caz, bazate pe metode incluzând căutare ramificată și legată , [13] locală , [14] algoritmi lacomi , [15] și programarea constrângerilor . [16] Metodologiile de calcul non-standard pentru găsirea fisurilor includ calculul ADN [17] și calculul cuantic adiabatic . [18] Problema maximă de clică a fost subiectul unei provocări de implementare sponsorizate de DIMACS în 1992-1993, [19] și o colecție de grafice utilizate ca etaloane pentru provocare este disponibilă publicului. [20]

Clase speciale de grafice

În acest grafic de permutare , fisurile maxime corespund celor mai lungi subsecvențe descrescătoare (4,3,1) și (4,3,2) din permutația definită.

Graficele plane și alte familii de grafice rare au fost discutate mai sus: au un număr liniar de fisuri maxime, de dimensiuni finite, care pot fi listate în timp liniar. [5] În special, pentru graficele plane, orice fisură poate avea cel mult patru vârfuri, conform teoremei lui Kuratowski .

Graficele perfecte sunt definite de proprietățile că numărul lor de fisuri este egal cu numărul lor cromatic și că această egalitate deține și în fiecare dintre subgrafele lor induse . Pentru grafice perfecte, este posibil să se găsească o fisură maximă în timp polinomial, folosind un algoritm bazat pe programare semidefinită . [21] Cu toate acestea, această metodă este complexă și necombinatorie, iar algoritmi specializați pentru găsirea fisurilor au fost dezvoltați pentru multe subclase de grafice perfecte. [22] În graficele complementare ale graficelor bipartite , teorema lui König permite rezolvarea problemei maxime a fisurilor folosind tehnici de cuplare . Într-o altă clasă de grafice perfecte , grafice de permutare , o clică maximă este o subsecvență descrescătoare care este mai lungă decât permutația care definește graficul și poate fi găsită folosind algoritmi cunoscuți pentru cea mai lungă problemă de subsecvență descrescătoare. [23] În graficele acordurilor , fisurile maxime sunt un subset al n fisurilor formate ca parte a unei ordonări de eliminare.

Î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 circular , proximitatea fiecărui vârf este un grafic de permutare, deci o fisură maximă poate fi găsită prin aplicarea algoritmului a graficului de permutare la fiecare proximitate. [24] În mod similar, într-un grafic pe disc (cu o reprezentare geometrică cunoscută), există un algoritm de timp polinomial pentru fisuri maxime bazat pe aplicarea algoritmului pentru complementele graficelor bipartite la vecinătățile comune ale perechilor de vârfuri. [25]

Problema algoritmică a găsirii unei fisuri maxime într-un grafic aleatoriu preluată din modelul Erdős-Rényi (în care fiecare margine apare cu probabilitatea 1/2, independent de celelalte margini) a fost sugerată de Karp (1976) . Deși numărul de fisuri al acestor grafice este foarte apropiat de 2 log 2 n , algoritmii simpli lacomi , precum și tehnici mai sofisticate de aproximare randomizată [26] găsesc doar fisuri cu dimensiunea log 2 n , iar numărul de fisuri maxime din astfel de grafice este, cu probabilitate mare, exponențială în log 2 n împiedicând o soluție polinomială care le listează pe toate. Datorită dificultății acestei probleme, mai mulți autori au investigat variante ale problemei în care graficul aleatoriu este mărit prin adăugarea unei clici mari, de dimensiune proporțională cu √ n . Este posibil să găsim această clică ascunsă cu probabilitate mare în timp polinomial, folosind fie metode spectrale [27], fie programare semidefinită . [28]

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 atât de apropiată de maximă încât 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, un caz care nu are sens pentru problema complementară a clicii, a lucrat și la algoritmi de aproximare care nu utilizează astfel de ipoteze de raritate. [29]

Feige (2004) descrie un algoritm de timp polinomial care găsește o fisură de dimensiunea Ω ((log n / log log n ) 2 ) în orice grafic având numărul de fisură Ω ( n / log k n ) pentru orice constantă k . Combinând acest algoritm pentru găsirea fisurilor în grafice cu numere de fisuri între n / log n și n / log 3 n cu un algoritm diferit de Boppana & Halldórsson (1992) pentru găsirea fisurilor în grafice cu numere mai mari de fisuri și alegerea unei fisuri a două vârfuri dacă ambii algoritmi nu pot găsi nimic, Feige oferă un algoritm de aproximare care găsește o fisură cu un număr de vârfuri într-un factor de O ( n (log log n ) 2 / log 3 n ) din maxim. Deși raportul de aproximare al acestui algoritm este slab, acesta este cel mai cunoscut până în prezent, iar rezultatele dificultății 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 o fisură. Vârfurile verzi formează o 3-clică și corespund unei sarcini satisfăcătoare. [30]

Problema deciziei clice este NP-completă . A fost una dintre cele 21 de probleme originale ale lui Richard Karp, demonstrate ca fiind NP-complete în lucrarea sa din 1972, Reducibility Among Combinatorial Problems . Această problemă a fost menționată și în eseul lui Stephen Cook care a introdus teoria problemelor NP-complete. Prin urmare, problema găsirii unei fisuri maxime este NP-dificilă: dacă s-ar putea rezolva, s-ar putea rezolva și problema deciziei, comparând dimensiunea maximă a fisurii cu parametrul de dimensiune dat ca intrare în problema deciziei.

Dovada lui Karp de completitudine NP este o reducere mult-la-unu a problemei de satisfacție booleană pentru formule conjunctive de formă normală , care sa dovedit a fi NP-completă în teorema Cook-Levin . [31] Dintr-o formulă FNC dată, 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 . Vârfurile sunt conectate printr-o margine dacă reprezintă atribuiri 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ția celălalt. Dacă k denotă numărul de clauze din formula FNC, atunci clicurile k- vertex din acest grafic reprezintă modalități de atribuire a unor valori de adevăr unor variabile ale acestuia pentru a satisface formula; prin urmare, formula este satisfăcătoare dacă și numai dacă există o clică cu k vârfuri.

Unele probleme NP complete (cum ar fi problema vânzătorului în grafice plane ) pot fi rezolvate într-un timp exponențial într-o funcție subliniară a parametrului n al dimensiunii de intrare. [32] Cu toate acestea, așa cum descriu Impagliazzo, Paturi și Zane (2001) , este puțin probabil ca astfel de limite să existe pentru problema fisurilor în grafice arbitrare, deoarece acestea ar implica limite subexponențiale similare pentru multe alte probleme standard NP-complete.

Complexitatea circuitelor

Un circuit monoton pentru a detecta o fisură k într-un grafic n- vârf pentru k = 3 și n = 4. Fiecare dintre cele 6 intrări codifică prezența sau absența unei anumite muchii (roșu) în graficul de intrare. Circuitul are o poartă ȘI internă pentru a detecta fiecare potențială k- crack.

Dificultatea de calcul a problemei crack-ului a însemnat că a fost utilizată pentru a dovedi diferite limite inferioare ale complexității circuitului . Deoarece existența unei fisuri de o dimensiune dată este o proprietate monotonă a graficelor (dacă există o fisură într-un grafic dat, aceasta va exista în orice supergraf), trebuie să existe un circuit monoton, care utilizează doar porți ȘI și porți SAU , pentru a rezolva problema deciziei fisurilor pentru o anumită dimensiune fixă ​​a fisurii în sine. Cu toate acestea, se poate arăta că dimensiunea acestor circuite este o funcție superpolinomială a numărului de vârfuri și a dimensiunii fisurii, exponențială în rădăcina cubică a numărului de vârfuri. [33] Chiar dacă este permis un număr mic de porți NU , complexitatea rămâne superpolinomială. [34] În plus, adâncimea unui circuit monoton pentru problema fisurilor folosind porți cu număr maxim limitat de linii de ventilare trebuie să fie de cel puțin un polinom de dimensiunea fisurii. [35]

Complexitatea arborilor de decizie

Un arbore de decizie simplu pentru a detecta prezența unui 3-crack într-un grafic cu 4 vârfuri. Utilizați până la 6 întrebări de la formularul „Există puna roșie?”, Potrivind limita optimă n ( n - 1) / 2.

Complexitatea (deterministă) a arborelui decizional în determinarea proprietății graficelor 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ă. Deoarece există cel mult n ( n - 1) / 2 întrebări posibile de răspuns, orice proprietate a graficelor poate fi determinată cu n ( n - 1) / 2 întrebări. È anche possibile definire la complessità casuale e quantistica dell'albero decisionale di una proprietà, il numero atteso di domande (per un'entrata del caso peggiore) a cui un algoritmo randomizzato o quantistico deve rispondere al fine di determinare correttamente se il grafo dato ha la proprietà in questione.

Poiché la proprietà di contenere una cricca è una proprietà monotona (aggiungere uno spigolo può fare soltanto in modo che esistano più cricche all'interno del grafo, non meno), essa è coperta dalla congettura di Aanderaa-Karp-Rosenberg , che afferma che la complessità deterministica dell'albero decisionale nel determinare una qualsiasi proprietà dei grafi monotona non banale è esattamente n ( n − 1)/2. Per gli alberi decisionali deterministici, fu dimostrato da Bollobás (1976) che una k -cricca (2 ≤ k ≤ n ) ha una complessità degli alberi esattamente di n ( n − 1)/2. Gli alberi decisionali deterministici richiedono una dimensione esponenziale per rilevare le cricche o una grande dimensione polinomiale per rilevare cricche di dimensione limitata. [36]

La congettura di Aanderaa-Karp-Rosenberg afferma anche che la complessità degli alberi decisionali randomizzati di funzioni monotone non banali è Θ(n 2 ). La congettura è risolta per la proprietà di contenere una k -cricca (2 ≤ k ≤ n ), poiché è noto che essa ha la complessità dell'albero decisionale randomizzato Θ(n 2 ). [37] Per gli alberi decisionali quantici, il limite inferiore più noto è Ω(n), ma non si conosce nessun algoritmo corrispondente per il caso di k ≥ 3. [38]

Intrattabilità a parametro fisso

La complessità parametrizzata [39] è lo studio di teoria della complessità dei problemi che sono forniti naturalmente di un piccolo parametro intero k , e per i quali il problema diventa più difficile al crescere di k , come il trovare k -cricche nei grafi. Si dice che un problema è trattabile a parametro fisso se c'è un algoritmo per risolverlo su entrate di dimensione n nel tempo f ( k ) n O(1) ; cioè, se può essere risolto in tempo polinomiale per qualsiasi valore fisso di k e in più se l'esponente del polinomio non dipende da k .

Per il problema della cricca, l'algoritmo di forza bruta ha un tempo di esecuzione O( n k k 2 ), e sebbene possa essere migliorato dalla moltiplicazione veloce tra matrici il tempo di esecuzione ha ancora un esponente che è lineare in k . Perciò, sebbene il tempo di esecuzione di algoritmi noti per il problema della cricca sia polinomiale per qualsiasi k fisso, questi algoritmi non sono sufficienti per la trattabilità a parametro fisso. Downey & Fellows (1995) definirono una gerarchia di problemi parametrizzati, la gerarchia W, che congetturarono non avesse algoritmi trattabili a parametro fisso; essi provarono che l'inisieme indipendente (o, equivalentemente, la cricca) è difficile per il primo livello di questa gerarchia, W[1] . Pertanto, secondo la loro congettura, la cricca non è trattabile a parametro fisso. Inoltre, questo risultato fornisce la base per le dimostrazioni della W[1] -difficoltà di molti altri problemi, e serve così come analogo del teorema di Cook-Levin per la complessità parametrizzata.

Chen et al. (2006) mostrarono che il problema della cricca non può essere risolto nel tempo a meno che non venga meno l' ipotesi del tempo esponenziale .

Sebbene sia improbabile che i problemi di elencare le cricche massimali o di trovare le cricche massime siano a trattabili a parametro fisso con il parametro k , esse possono essere a trattabili a parametro fisso per altri parametri di complessità delle istanze. Ad esempio, è noto che entrambi i problemi sono a trattabili a parametro fisso quando sono parametrizzati in base alla degenerazione del grafo delle entrate. [12]

Difficoltà di approssimazione

Un grafo di relazioni di compatibilità tra campioni a 2 bit di stringhe di dimostrazione a 3 bit. Ciascuna cricca massimale (triangolo) di questo grafo rappresenta tutti i modi di campionare una singola stringa da 3 bit. La dimostrazione dell'inapprossimabilità del problema della cricca coinvolge sottografi indotti di grafi analogamente definiti per numeri maggiori di bit.

La complessità computazionale di approssimare il problema della cricca è studiata da molto tempo; ad esempio, Garey & Johnson (1978) osservarono che, a causa del fatto che il numero di cricca assume valori interi piccoli ed è NP-difficile da computare, non può avere uno schema di approssimazione in tempo pienamente polinomiale . Tuttavia, poco di più si seppe fino ai primi anni 1990, quando parecchi autori cominciarono a fare connessioni tra l'approssimazione delle cricche massime e le dimostrazioni verificabili probabilisticamente , e usarono queste connessioni per dimostrare i risultati della difficoltà di approssimazione per il problema della cricca massima. [4] [40] Dopo molti miglioramenti in questi risultati è ora noto che, a meno che P = NP , non ci può essere nessun algoritmo in tempo polinomiale che approssima la cricca massima entro un fattore migliore di O( n 1 − ε ), per qualsiasi ε > 0. [41]

L'idea generica di questi risultati di inapprossimabilità [42] è formare un grafo che rappresenta un sistema di dimostrazioni verificabili probabilisticamente per un problema NP-completo come la soddisfacibilità. Un sistema di dimostrazione di questo tipo è definito da una famiglia di stringhe di dimostrazione (sequenze di bit) e da verificatori di dimostrazione: algoritmi che, dopo una quantità polinomiale di computazione su una data istanza di soddisfacibilità, eaaminano un piccolo numero di bit della stringa di dimostrazione scelti casualmente e, sulla base di quell'esame, dichiarano che è o una dimostrazione valida o una dimostrazione invalida. Le false negazioni non sono consentite: una dimostrazione valida deve essere sempre dichiarata valida, ma una dichiarazione invalida può essere dichiarata valida finché la probabilità che un verificatore faccia un errore di questo tipo è bassa. Per trasformare un sistema di dimostrazione verificabile probabilisticamente in un problema della cricca, si forma un grafo nel quale i vertici rappresentano tutti i modi possibili in cui un verificatore di dimostrazioni potrebbe leggere una sequenza di bit di stringhe di dimostrazione e finire accettando la dimostrazione. Due vertici sono connessi da uno spigolo ogni volta che le due esecuzioni del verificatore di dimostrazioni che essi descrivono concordano sui valori dei bit della stringa di dimostrazione che entrambe esaminano. Le cricche massimali in questo grafo consistono nelle esecuzioni per una singola stringa di dimostrazione del verificatore di dimostrazioni che ha il compito di fare l'accettazione, e una di queste cricche è grande se e solo se esiste una stringa di dimostrazione che molti verificatori di dimostrazioni accettano. Se l'istanza originale di soddisfacibilità è soddisfacibile, ci sarà una grande cricca definita da una stringa di dimostrazione valida per quell'istanza, ma se l'istanza originale non è soddisfacibile, allora tutte le stringhe di dimostrazione sono invalide, qualsiasi stringa di dimostrazione ha solo un piccolo numero di verificatori che l'accettano erroneamente e tutte le cricche sono piccole. Perciò, se si potesse distinguere in tempo polinomiale tra i grafi che hanno grandi cricche ei grafi nei quali le cricche sono piccole, si potrebbe usare questa abilità per distinguere i grafi generati dalle istanze soddisfacibili e insoddisfacibili del problema della soddisfacibilità, non possibile a meno che P = NP. Un'approssimazione accurata in tempo polinomiale al problema della cricca consentirebbe a questi due insiemi di grafi di essere distinti l'uno dall'altro, ed è perciò anch'essa impossibile.

Programmi liberi per la ricerca della massima cricca

Nome
 Licenza Linguaggio API Breve info
NetworkX BSD Python soluzione approssimata, vedi la routine max_clique [ collegamento interrotto ]
maxClique CRAPL Java algoritmi esatti e istanze DIMACS
OpenOpt BSD Python soluzioni esatte e approssimate, possibilità di specificare i nodi che devono essere
inclusi / esclusi; vedi la classe MCP Archiviato il 3 ottobre 2013 in Internet Archive . per maggiori dettagli ed esempi

Note

  1. ^ a b c d e Per una rassegna di questi algoritmi di questi algoritmi e per le definizioni di base usate in questo articolo, vedi Bomze, Budinich, Pardalos & Pelillo (1999) e Gutin (2004) .
  2. ^ Per maggiori dettagli e riferimenti, vedi cricca (teoria dei grafi) .
  3. ^ I sottografi completi fanno una prima apparizione nella letteratura matematica nella riformulazione della teoria dei grafi della teoria di Ramsey da parte di Erdős & Szekeres (1935) .
  4. ^ a b Gina Kolata, In a Frenzy, Math Enters Age of Electronic Mail , in New York Times , 26 giugno 1990.
  5. ^ a b c d Chiba & Nishizeki (1985) .
  6. ^ Ad es., vedi Downey & Fellows (1995) .
  7. ^ Itai & Rodeh (1978) forniscono un algoritmo con tempo di esecuzione O( m 3/2 ) che trova un triangolo se ne esiste uno, ma non elenca tutti i triangoli; Chiba & Nishizeki (1985) elencano tutti i triangoli nel tempo O( m 3/2 ).
  8. ^ Eisenbrand2004 , Eisenbrand & Grandoni (2004) ; Kloks, Kratsch & Müller (2000) ; Nešetřil & Poljak (1985) ; Vassilevska & Williams (2009) ; Yuster (2006) .
  9. ^ Tomita, Tanaka & Takahashi (2006) .
  10. ^ Cazals & Karande (2008) ; Eppstein & Strash (2011) .
  11. ^ Rosgen & Stewart (2007) .
  12. ^ a b Eppstein, Löffler & Strash (2010) .
  13. ^ Balas & Yu (1986) ; Carraghan & Pardalos (1990) ; Pardalos & Rogers (1992) ; Östergård (2002) ; Fahle (2002) ; Tomita & Seki (2003) ; Tomita & Kameda(2007) ; Konc & Janežič (2007) .
  14. ^ Battiti & Protasi (2001) ; Katayama, Hamamoto & Narihisa (2005) .
  15. ^ Abello, Pardalos & Resende (1999) ; Grosso, Locatelli & Della Croce (2004) .
  16. ^ Régin (2003) .
  17. ^ Ouyang et al. (1997) . Sebbene il titolo si riferisca alle cricche massimali, il problema che questo saggio risolve è in effetti il problema della cricca massima.
  18. ^ Childs et al. (2002) .
  19. ^ Johnson & Trick (1996) .
  20. ^ DIMACS challenge graphs for the clique problem Archiviato il 18 dicembre 2009 in Wikiwix., consultato il 17-12-2009.
  21. ^ Grötsche, Lovász & Schrijver (1988) .
  22. ^ Golumbic (1980) .
  23. ^ Golumbic (1980) , p. 159. Ecen, Pnueli & Lempel (1972) forniscono un algoritmo alternativo in tempo quadratico per le cricche massime nei grafi di comparabilità , una classe di grafi perfetti più vasta che include i grafi di permutazione come caso speciale.
  24. ^ Gavril (1973) ; Golumbic (1980) , p. 247.
  25. ^ Clark, Colbourn & Johnson (1990) .
  26. ^ Jerrum (1992) .
  27. ^ Alon, Krivelevich & Sudakov (1998) .
  28. ^ Feige & Krauthgamer (2000) .
  29. ^ Boppana & Halldórsson (1992) ; Feige (2004) ; Halldórsson (2000) .
  30. ^ Adattato da Sipser1996 , Sipser (1996) .
  31. ^ Cook (1971) dà essenzialmente la stessa riduzione, da 3-SAT invece della soddisfacibilità, per mostrare che l' isomorfismo di sottografi è NP-completo.
  32. ^ Lipton & Tarjan (1980) .
  33. ^ Alon & Boppana (1987) . Per limiti anteriori e più deboli sul problema della cricca, vedi Valiant (1983) e Razborov (1985) .
  34. ^ Amano1998 , Amano & Maruoka (1998) .
  35. ^ Goldmann & Håstad (1992) usarono la complessità della comunicazione per dimostrare questo risultato.
  36. ^ Wegener (1988) .
  37. ^ Per esempio, questo consegue da Gröger (1992) .
  38. ^ Childs & Eisenberg (2005) ; Magniez, Santha & Szegedy (2007) .
  39. ^ Downey & Fellows (1999) .
  40. ^ Feige et al. (1991) ; Arora & Safra (1998) ; Arora1998b , Arora et al. (1998) .
  41. ^ Håstad (1999) dimostrò l'inapprossimabilità per questo rapporto usando un'assunzione teorica di complessità più forte, la disuguaglianza di NP e ZPP ; Khot (2001) descrisse più precisamente il rapporto di inapprossimazione, e Zuckerman (2006) derandomizzò la costruzione indebolendo la sua assunzione a P ≠ NP.
  42. ^ Questa riduzione è dovuta originariamente a Feige et al. (1991) e usata in tutte le successive dimostrazioni di inapprossimabilità; le dimostrazioni differiscono nelle forze e nei dettagli dei sistemi di dimostrazioni verificabili probabilisticamente su cui si basano.

Bibliografia

Estratto da " https://it.wikipedia.org/w/index.php?title=Problema_della_cricca&oldid=117516582 "