Problema della cricca

In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi ("cricche") in un grafo, cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa.

Per esempio, il problema della cricca massima nasce nel seguente scenario del mondo reale. Si consideri una rete sociale, dove i vertici del grafo rappresentano le persone, e gli spigoli del grafo rappresentano le reciproche conoscenze. Per trovare un sottoinsieme più grande di persone che si conoscono tutte tra di loro, si possono ispezionare sistematicamente tutti i sottoinsiemi, un processo che consuma troppo tempo per essere pratico per reti sociali che comprendano più di qualche dozzina di persone. Sebbene questa ricerca mediante forza bruta possa essere migliorata da algoritmi più efficienti, tutti questi algoritmi impiegano un tempo esponenziale per risolvere il problema. Perciò, gran parte della teoria sul problema della cricca è dedicata a identificare tipi speciali di grafo che ammettano algoritmi più efficienti, o a stabilire la difficoltà computazionale del problema generale in vari modelli di computazione.^[1] Insieme alle sue applicazioni nelle reti sociali, il problema della cricca ha anche molte applicazioni in bioinformatica e in chimica computazionale.^[2]

I problemi della cricca includono:

• trovare la cricca massima (una cricca con il più grande numero di vertici),
• trovare una cricca con il peso massimo in un grafo pesato,
• elencare tutte le cricche massimali (cricche che non possono essere ampliate),
• risolvere il problema decisionale di verificare se un grafo contiene una cricca più grande di una data dimensione.

Questi problemi sono tutti difficili: il problema decisionale della cricca è NP-completo (uno dei 21 problemi NP-completi di Karp), il problema di trovare la cricca massima è sia intrattabile a parametro fisso, sia difficile da approssimare, ed elencare tutte le cricche massimali può richiedere un tempo esponenziale in quanto esistono grafi con un numero esponenziale di cricche massimali. Nondimeno, ci sono algoritmi per questi problemi che si eseguono in tempo esponenziale o che gestiscono certi grafi di entrata più specializzati in tempo polinomiale.^[1]

Sebbene i sottografi completi siano studiati da più tempo in matematica,^[3] il termine "cricca" (clique nell'originale inglese) e il problema di elencare algoritmicamente le cricche vengono entrambi dalle scienze sociali, dove i sottografi completi sono usati per modellare le cricche sociali, gruppi di persone che si conoscono tutte fra di loro. La terminologia della "cricca" viene da Luce & Perry (1949), e il primo algoritmo per risolvere il problema della cricca è quello di Harari & Ross (1957),^[1] che erano motivati dall'applicazione sociologica.

A partire dal lavoro di Harary e Ross, molti altri hanno escogitato algoritmi per varie versioni del problema della cricca.^[1] Negli anni 1970, i ricercatori cominciarono a studiare questi algoritmi dal punto di vista dell'analisi del caso peggiore; vedi, per esempio, Tarjan & Trojanowski (1977), un primo lavoro sulla complessità del caso peggiore nel problema della cricca massima. Sempre negli anni 1970, a cominciare dal lavoro di Cook (1971) e Karp (1972), i ricercatori iniziarono a trovare giustificazioni matematiche per la difficoltà percepita del problema della cricca nella teoria della NP-completezza e dei risultati correlati sull'intrattabilità. Negli anni 1990, una serie di studi rivoluzionari iniziati con Feige et al. (1991) e riportati all'epoca dai principali giornali,^[4] mostrarono che non è neanche possibile approssimare il problema in modo accurato ed efficiente.

Un grafo indiretto è formato da un insieme finito di vertici e da un insieme di coppie non ordinate di vertici, che sono chiamati spigoli. Per convenzione, nell'analisi degli algoritmi, il numero di vertici nel grafo è denotato da n e il numero di spigoli è denotato da m. Una cricca in un grafo G è un sottografo completo di G; cioè, è un sottoinsieme S di vertici tale che ogni due vertici in S sono connessi da uno spigolo in G. Una cricca massimale è una cricca alla quale non possono essere aggiunti altri vertici; una cricca massima è una cricca che include il numero di vertici più grande possibile, e il numero di cricca ω(G) è il numero di vertici in una cricca massima di G.^[1]

Sono stati studiati parecchi problemi strettamente collegati alla ricerca delle cricche.

• Nel problema della cricca massima, l'entrata è un grafo indiretto, e l'uscita è una cricca massima del grafo. Se ci sono cricche massime mutiple, solo una deve essere l'uscita.
• Nel problema della cricca massima ponderata, l'entrata è un grafo indiretto con i pesi sui suoi vertici (o, meno frequentemente, spigoli) e l'uscita è una cricca con il massimo peso totale. Il problema della cricca massima è il caso speciale in cui i pesi sono tutti uguali.
• Nel problema dell'elencazione delle cricche massimali, l'entrata è un grafo indiretto, e l'uscita è un elenco di tutte le sue cricche massimali. Il problema della cricca massima può essere risolto usando come subroutine un algoritmo per il problema dell'elencazione delle cricche massimali, perché la cricca massima deve essere inclusa fra tutte le cricche massimali.
• Nel problema della k-cricca, l'entrata è un grafo indiretto e un numero k, e l'uscita è una cricca di dimensione k se ne esiste una (o, talvolta, tutte le cricche di dimensione k).
• Nel problema di decisione della cricca, l'entrata è un grafo indiretto e un numero k, e l'uscita è un valore booleano: vero se il grafo contiene una k-cricca, e falso altrimenti.

I primi quattro di questi problemi sono tutti importanti in applicazioni pratiche; il problema di decisione della cricca non lo è, ma è necessario per applicare la teoria della NP-completezza ai problemi di ricerca delle cricche.

Il problema della cricca e il problema dell'insieme indipendente sono complementari: una cricca in G è un insieme nel grafo complemento di G e viceversa. Perciò, molti risultati computazionali possono essere applicati ugualmente bene a entrambi i problemi, e alcuni saggi di ricerca non distinguono chiaramente tra i due problemi. Tuttavia, i due problemi hanno proprietà diverse quando sono applicati a famiglie ristrette di grafi; per esempio, il problema della cricca può essere risolto in tempo polinomiale per i grafi planari,^[5] mentre il problema dell'insieme indipendente rimane NP-difficile sui grafi planari.

Una cricca massimale, talvolta chiamata massimale con inclusione, è una cricca che non è inclusa in una cricca più grande. Si noti, perciò, che ogni cricca è contenuta in una cricca massima.

Le cricche massimali possono essere molto piccole. Un grafo può contenere una cricca non massimale con molti vertici e una cricca separata di dimensione 2 che è massimale. Mentre una cricca massima (cioè, più grande) è necessariamente massimale, l'inverso non vale. Ci sono alcuni tipi di grafi in cui ogni cricca è massima (i complementi dei grafi ben coperti, che includono in particolare grafi completi, grafi senza triangoli senza vertici isolati, grafi multipartiti completi e k-alberi), ma altri grafi hanno cricche massimali che non sono massime.

Trovare una cricca massimale è immediato: partendo da una cricca arbitraria (per esempio, un singolo vertice), si fa crescere la cricca attuale un vertice alla volta iterando sui vertici rimanenti del grafo, aggiungendo un vertice se è connesso a ciascun vertice della cricca attuale e scartandolo altrimenti. Questo algoritmo funziona in tempo lineare. A causa della facilità di trovare le cricche massimali e della loro dimensione potenziale, maggiore attenzione è stata dedicata al problema algoritmico, molto più difficile, di trovare una cricca massima o altrimenti grande di quanta ne sia stata data al problema di trovare una singola cricca massima.

Un algoritmo di forza bruta per testare se un grafo G contiene una cricca con k vertici, e per trovare qualsiasi cricca di questo tipo che esso contiene, deve esaminare ciascun sottografo con almeno k vertici e controllare per vedere se forma una cricca. Questo algoritmo impiega il tempo O(n^k k²): ci sono O(n^k) sottografi da controllare, ciascuno dei quali ha O(k²) spigoli la cui presenza in G deve essere controllata. Pertanto, il problema può essere risolto in tempo polinomiale ogni qual volta k sia una costante fissa. Quando k fa parte dell'entrata del problema, tuttavia, il tempo è esponenziale.^[6]

Il più semplice caso non banale del problema di trovare una cricca è trovare un triangolo in un grafo, o equivalentemente di determinare se il grafo è senza triangoli. In un grafo con m spigoli, ci possono essere al più Θ(m^3/2) triangoli; il caso peggiore avviene quando G è esso stesso una cricca. Perciò, gli algoritmi per elencare tutti i triangoli devono impiegare almeno il tempo Ω(m^3/2) nel caso peggiore, e si conoscono algoritmi che si abbinano a questo limite temporale.^[7] Per esempio, Chiba & Nishizeki (1985) descrivono un algoritmo che ordina i vertici dal grado più alto al più basso e poi itera attraverso ciascun vertice v nell'elenco ordinato, cercando triangoli che includono v e che non includono nessun vertice precedente della lista. Per fare questo l'algoritmo marca tutti i vicini di v, ricerca attraverso tutti gli spigoli incidenti a un vicino di v producendo come uscita un triangolo per ogni spigolo che ha due punti estremi marcati, e poi rimuove le marcature e cancella v dal grafo. Come mostrano gli autori, il tempo per questo algoritmo è proporzionale all'arboricità del grafo (a(G)) per il numero degli spigoli, che è O(m a(G)). Poiché l'arboricità è al più O(m^1/2), questo algoritmo funziona nel tempo O(m^3/2). Più in generale, tutte le cricche con k vertici possono essere elencate da un algoritmo simile che impiega un tempo proporzionale al numero di spigoli per la (k − 2)-esima potenza dell'arboricità.^[5] Per i grafi di arboricità costante, come i grafi planari (o in generale i grafi di qualsiasi famiglia di grafi chiusi sui minori di tipo non banale), questo algoritmo impiega il tempo O(m), che è ottimale dal momento che è lineare nella dimensione dell'entrata.

Se si desidera solo un singolo triangolo, o l'assicurazione che il grafo sia senza triangoli, sono possibili algoritmi più veloci. Come osservano Itai & Rodeh (1978), il grafo contiene un triangolo se e solo se la sua matrice delle adiacenze e il quadrato della matrice delle adiacenze contengono immissioni diverse da zero nella stessa cella; perciò tecniche di moltiplicazione veloce tra matrici come l'algoritmo di Coppersmith-Winograd si possono applicare per trovare i triangoli nel tempo O(n^2,376), che può essere più veloce di O(m^3/2) per grafi sufficientemente densi. Alon, Yuster & Zwick (1994) hanno migliorato l'algoritmo O(m^3/2) per trovare i triangoli a O(m^1,41) usando la moltiplicazione veloce tra matrici. Questa idea di usare la moltiplicazione veloce tra matrici per trovare i triangoli è stata estesa anche ai problemi di trovare k-cricche per valori più grandi di k.^[8]

Secondo un risultato di Moon & Moser (1965), qualsiasi grafo con n vertici ha al più 3^n/3 cricche massimali. L'algoritmo di Bron-Kerbosch è una procedura ricorsiva di ritorno all'indietro (backtracking) di Bron & Kerbosch (1973) che accresce una cricca candidata considerando un vertice alla volta, aggiungendolo o alla cricca candidata o a un insieme di vertici esclusi che non possono essere nella cricca, ma devono avere qualche non vicino nella cricca finale; si può dimostrare che le varianti di questo algoritmo hanno un tempo di esecuzione nel caso peggiore di O(3^n/3).^[9] Perciò, questo fornisce una soluzione ottimale, nel caso peggiore, al problema di elencare tutti gli insiemi indipendenti massimali; inoltre, è stato ampiamente riportato che l'algoritmo di Bron-Kerbosch è in pratica più veloce delle sue alternative.^[10]

Come mostrarono Tsukiyama, Ide, Ariyoshi & Shirakawa (1977), è anche possibile elencare tutte le cricche massimali in un grafo in una quantità di tempo che è polinomiale per ogni cricca generata. Un algoritmo come il loro nel quale il tempo di esecuzione dipende dalla dimensione dell'uscita è noto come algoritmo sensibile all'uscita. Il loro algoritmo si basa sulle seguenti due osservazioni, che collegano le cricche massimali del grafo dato G alle cricche massimali di un grafo G \ v formato rimuovendo un vertice arbitrario v da G:

• Per ogni cricca massimale C di G \ v, o C continua a formare una cricca massimale in G, o C ⋃ {v} forma una cricca massimale in G. Perciò, G ha almeno altrettante cricche massimali di G \ v.
• Ciascuna cricca massimale in G che non contenga v è una cricca massimale in G \ v, e ciascuna cricca massimale in G che non contiene v può essere formata da una cricca massimale C in G \ v aggiungendo v e rimuovendo i non vicini di v da C.

Usando queste osservazioni esse possono generare tutte le cricche massimali in G mediante un algoritmo ricorsivo che, per ciascuna cricca massimale C in G \ v, produce come uscita C e la cricca formata aggiungendo v a C e rimuovendo tutti i non vicini di v. Tuttavia, alcune cricche di G possono essere generate in questo modo da più di una cricca genitrice di G \ v, così eliminano i duplicati producendo come uscita una cricca in G solo quando la sua genitrice in G \ v è lessicograficamente massima fra tutte possibili cricche genitrici. Sulla base di questo principio, essi mostrano che tutte le cricche massimali in G possono essere generate nel tempo O(mn) per ogni cricca, dove m è il numero di spigoli in G ed n è il numero di vertici; Chiba & Nishizeki (1985) migliorano questo valore a O(ma) per ogni cricca, dove a è l'arboricità del grafo dato. Makino & Uno (2004) forniscono un algoritmo alternativo sensibile all'uscita basato sulla moltiplicazione veloce tra matrici, e Johnson & Yannakakis (1988) mostrano che è anche possibile elencare tutte le cricche massimali in ordine lessicografico con un ritardo polinomiale per ogni cricca, sebbene l'inverso di quest'ordine sia NP-difficile da generare.

Sulla base di questo risultato, è possibile elencare tutte le cricche massimali in tempo polinomiale, per famiglie di grafi in cui il numero di cricche è limitato polinomialmente. Queste famiglie includono i grafi cordali, i grafi completi, i grafi senza triangoli, i grafi d'intervallo, i grafi di bossicità limitata e i grafi planari.^[11] In particolare, i grafi planari e, più generalmente, qualsiasi famiglia di grafi che è sia sparsa (avendo come numero di spigoli al massimo una costante per il numero di vertici), sia chiusa in base all'operazione di prendere i sottografi, ha O(n) cricche, al massimo di dimensione costante, che possono essere elencate in tempo lineare.^[5][12]

È possibile trovare la cricca massima, o il numero di cricca, di un grafo arbitrario a n vertici nel tempo O(3^n/3) = O(1,4422ⁿ) usando uno degli algoritmi descritti sopra per elencare tutte le cricche massimali del grafo e restituire quella più grande. Tuttavia, per questa variante del problema della cricca sono possibili limiti temporali migliori per il caso peggiore. L'algoritmo of Tarjan & Trojanowski (1977) risolve questo problema nel tempo O(2^n/3) = O(1,2599ⁿ); è uno schema ricorsivo di ritorno all'indietro (backtracking) simile a quello dell'algoritmo di Bron-Kerbosch, ma è in grado di eliminare alcune chiamate ricorsive quando si può dimostrare che è garantito che qualche altra combinazione di vertici non usata nella chiamata conduce a una soluzione almeno altrettanto buona. Jian (1986) migliorò questo in O(2^0,304n) = O(1,2346ⁿ). Robson (1986) lo migliorò nel tempo O(2^0,276n) = O(1,2108ⁿ), a spese di un maggiore uso di spazio, mediante uno schema di ritorno all'indietro simile con un'analisi dei casi più complicata, insieme a una tecnica di programmazione dinamica nella quale la soluzione ottimale è precalcolata per tutti i sottografi piccoli connessi del grafo complemento e queste soluzioni parziali sono usate per abbreviare la rercursione del ritorno all'indietro. L'algoritmo più veloce oggi conosciuto è quello dovuto a Robson (2001), che si esegue nel tempo O(2^0,249n) = O(1,1888ⁿ).

Ci sono state estese ricerche anche su algoritmi euristici per risolvere i problemi delle cricche massime senza garanzie sui tempi di esecuzione del caso peggiore, basati su metodi che includono il branch and bound,^[13] la ricerca locale,^[14] gli algoritmi golosi,^[15] e la programmazione a vincoli.^[16] Le metodologie di computazione non standard per trovare le cricche includono la computazione a DNA^[17] e la computazione quantistica adiabatica.^[18] Il problema della cricca massima era l'argomento di una sfida di implementazione sponsorizzato dal DIMACS nel 1992–1993,^[19] e una collezione di grafi usati come parametri di riferimento per la sfida è disponibile pubblicamente.^[20]

I grafi planari, e altre famiglie di grafi sparsi, sono stati discussi sopra: essi hanno un numero lineare di cricche massimali, di dimensione limitata, che possono essere elencati in tempo lineare.^[5] In particolare, per i grafi planari, qualsiasi cricca può avere al massimo quattro vertici, in base al teorema di Kuratowski.

I grafi perfetti sono definiti dalle proprietà che il loro numero di cricca uguaglia il loro numero cromatico e che questa uguaglianza vale anche in ciascuno dei loro sottografi indotti. Per i grafi perfetti, è possibile trovare una cricca massima in tempo polinomiale, usando un algoritmo basato sulla programmazione semidefinita.^[21] Tuttavia, questo metodo è complesso e non combinatorio, e algoritmi specializzati per la ricerca di cricche sono stati sviluppati per molte sottoclassi di grafi perfetti.^[22] Nei grafi complemento dei grafi bipartiti, il teorema di König permette al problema della cricca massima di essere risolto usando tecniche per l'accoppiamento. In un'altra classe di grafi perfetti, i grafi di permutazione, una cricca massima è una sottosequenza decrescente più lunga della permutazione che definisce il grafo e si può trovare usando algoritmi conosciuti per il problema della sottosequenza decrescente più lunga.^[23] Nei grafi cordali, le cricche massimali sono un sottoinsieme delle n cricche formate come parte di un ordinamento di eliminazione.

In alcuni casi, questi algoritmi possono essere estesi pure ad altre classi di grafi, non perfette: per esempio, in un grafo a cerchio, la vicinanza di ciascun vertice è un grafo di permutazione, così una cricca massima si può trovare applicando l'algoritmo del grafo di permutazione a ciascuna vicinanza.^[24] Similmente, in un grafo di dischi (con una rappresentazione geometrica nota), c'è un algoritmo in tempo polinomiale per le cricche massime basato sull'applicazione dell'algoritmo per i complementi di grafi bipartiti alle vicinanze condivise delle coppie di vertici.^[25]

Il problema algoritmico di trovare una cricca massima in un grafo casuale tratto dal modello di Erdős-Rényi (nel quale ciascuno spigolo appare con probabilità 1/2, indipendentemente dagli altri spigoli) fu suggerito da Karp (1976). Sebbene il numero di cricca di tali grafi sia molto vicino a 2 log₂n, semplici algoritmi golosi come pure più sofisticate tecniche di approssimazione randomizzate^[26] trovano solo cricche con dimensione log₂n, e il numero di cricche massimali in tali grafi è, con alta probabilità, esponenziale in log²n impedendo una soluzione polinomiale che le elenchi tutte. A causa della difficoltà di questo problema, parecchi autori hanno investigato varianti del problema nel quale il grafo casuale è aumentato aggiungendo una grande cricca, di dimensione proporzionale a √n. È possibile trovare questa cricca nascosta con alta probabilità in tempo polinomiale, usando o metodi spettrali^[27] o la programmazione semidefinita.^[28]

Parecchi autori hanno considerato algoritmi di approssimazione che tentano di trovare una cricca o un insieme indipendente che, sebbene non massimi, abbiano dimensione tanto vicina al massimo da poter essere trovati in tempo polinomiale. Sebbene gran parte di questo lavoro si sia focalizzata su insiemi indipendenti in grafi sparsi, un caso che non ha senso per il problema complementare della cricca, si è lavorato anche su algoritmi di approssimazione che non usano tali assunzioni di sparsità.^[29]

Feige (2004) descrive un algoritmo in tempo polinomiale che trova una cricca di dimensione Ω((log n/log log n)²) in qualsiasi grafo che abbia numero di cricca Ω(n/log^kn) per qualsiasi costante k. Combinando questo algoritmo per trovare cricche in grafi con numeri di cricca tra n/log n e n/log³n con un diverso algoritmo di Boppana & Halldórsson (1992) per trovare cricche in grafi con numeri di cricca superiori, e scegliendo una cricca a due vertici se entrambi gli algoritmi non riescono a trovare niente, Feige fornisce un algoritmo di approssimazione che trova una cricca con un numero di vertici entro un fattore di O(n(log log n)²/log³n) del massimo. Sebbene il rapporto di approssimazione di questo algoritmo sia debole, è il più conosciuto ad oggi, e i risultati sulla difficoltà di approssimazione descritti sotto suggeriscono che non possa esserci un algoritmo di approssimazione con rapporto di approssimazione significativamente meno che lineare.

Il problema decisionale della cricca è NP-completo. Era uno dei 21 problemi originali di Richard Karp dimostrati come NP-completi nel suo saggio del 1972 Reducibility Among Combinatorial Problems. Questo problema fu menzionato anche nel saggio di Stephen Cook che introduceva la teoria dei problemi NP-completi. Pertanto, il problema di trovare una cricca massima è NP-difficile: se si potesse risolverlo, si potrebbe anche risolvere il problema decisionale, confrontando la dimensione della cricca massima con il parametro della dimensione dato come entrata nel problema decisionale.

La dimostrazione della NP-completezza di Karp è una riduzione molti a uno del problema di soddisfacibilità booleana per le formule in forma normale congiuntiva, che fu dimostrato essere NP-completo nel teorema di Cook-Levin.^[31] Da una data formula FNC, Karp forma un grafo che ha un vertice per ogni coppia (v,c), dove v è una variabile o la sua negazione e c è una clausola nella formula che contiene v. I vertici sono connessi da uno spigolo se rappresentano assegnazioni di variabili compatibili per diverse clausole: ossia, c'è uno spigolo da (v,c) a (u,d) ogni volta che c ≠ d e u e v non sono l'uno la negazione dell'altro. Se k denota il numero di clausole nella formula FNC, allora le cricche con k vertici in questo grafo rappresentano modi di assegnare valori di verità ad alcune delle sue variabili al fine di soddisfare la formula; perciò, la formula è soddisfacibile se e solo se esiste una cricca con k vertici.

Alcuni problemi NP completi (come il problema del commesso viaggiatore nei grafi planari) possono essere risolti in un tempo che è esponenziale in una funzione sublineare del parametro n della dimensione dell'entrata.^[32] Tuttavia, come descrivono Impagliazzo, Paturi & Zane (2001), è improbabile che esistano tali limiti per il problema della cricca in grafi arbitrari, in quanto implicherebbero limiti similmente subesponenziali per molti altri problemi NP-completi standard.

La difficoltà computazionale del problema della cricca ha fatto sì che fosse usato per dimostrare vari limiti inferiori nella complessità dei circuiti. Poiché l'esistenza di una cricca di una data dimensione è una proprietà monotona dei grafi (se esiste una cricca in un dato grafo, esisterà in qualsiasi supergrafo), deve esistere un circuito monotono, che usa solo porte AND e porte OR, per risolvere il problema decisionale della cricca per una data dimensione fissa della cricca stessa. Tuttavia, si può dimostrare che la dimensione di questi circuiti è una funzione superpolinomiale del numero dei vertici e della dimensione della cricca, esponenziale nella radice cubica del numero dei vertici.^[33] Anche se sono ammesse un piccolo numero di porte NOT, la complessità rimane superpolinomiale.^[34] In più, la profondità di un circuito monotono per il problema della cricca che usa porte con numero massimo di linee d'ingresso (fan-in) limitato deve essere almeno un polinomio della dimensione della cricca.^[35]

La complessità (deterministica) dell'albero decisionale nel determinare la proprietà dei grafi è il numero di domande della forma "C'è uno spigolo tra il vertice u e il vertice v?" a cui si deve rispondere nel caso peggiore per determinare se un grafo ha una particolare proprietà. Ossia, È l'altezza minima di un albero decisionale booleano per il problema. Dal momento che ci sono al massimo n(n − 1)/2 domande possibili a cui rispondere, qualsiasi proprietà dei grafi può essere determinata con n(n − 1)/2 domande. È 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²). 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²).^[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]

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^kk²), 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 ${\displaystyle n^{o(k)}}$ 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]

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 e i 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.

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