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.

L'algoritmo forza bruta trova una 4-cricca in questo grafo a 7 vertici (il complemento del grafo cammino a 7 vertici) controllando sistematicamente tutti i sottografi a 4 vertici C(7,4)=35 per verificare la completezza.

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]

Storia

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.

Definizioni

Lo stesso argomento in dettaglio: Cricca (teoria dei grafi).

Il grafo mostrato ha una sola cricca massima, il triangolo {1,2,5}, e altre quattro cricche massimali, le coppie {2,3}, {3,4}, {4,5} e {4,6}.

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.

Algoritmi

Massimale contro massima

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.

Cricche di dimensione fissa

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]

Elencare tutte le cricche massimali

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]

Trovare le cricche massime in grafi arbitrari

È 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]

Classi speciali di grafi

In questo grafo di permutazione, le cricche massime corrispondono alle sottosequenze decrescenti più lunghe (4,3,1) e (4,3,2) della permutazione definita.

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]

Algoritmi di approssimazione

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.

Limiti inferiori

NP-completezza

L'istanza di soddisfacibilità 3-CNF (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) ridotta a cricca. I vertici verdi formano una 3-cricca e corrispondono a un'assegnazione soddisfacente.^[30]

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.

Complessità dei circuiti

Un circuito monotono per rilevare una k-cricca in un grafo a n vertici per k = 3 ed n = 4. Ciascuna delle 6 entrate codifica la presenza o l'assenza di un particolare spigolo (rosso) nel grafo dell'entrata. Il circuito una porta AND interna per rilevare ogni potenziale k-cricca.

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]

Complessità degli alberi decisionali

Un semplice albero decisionale per rilevare la presenza di una 3-cricca in un grafo a 4 vertici. Usa fino a 6 domande della forma "Esiste il cuneo rosso?", abbinandosi al limite ottimale n(n − 1)/2.

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]

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^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]

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

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. Per una rassegna 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. Gina Kolata, In a Frenzy, Math Enters Age of Electronic Mail, in New York Times, 26 giugno 1990.
5. 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. 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

• J. Abello, P. M. Pardalos e M. G. C. Resende, On maximum clique problems in very large graphs, in J. Abello e J. Vitter (a cura di), External Memory Algorithms, DIMACS Serie on Discrete Mathematics and Theoretical Computer Science, vol. 50, American Mathematical Society, 1999, 119–130, ISBN 0-8218-1184-3. URL consultato il 26 marzo 2014 (archiviato dall'url originale il 29 febbraio 2012).
• N. Alon e R. Boppana, The monotone circuit complexity of boolean functions, in Combinatorica, vol. 7, n. 1, 1987, 1–22, DOI:10.1007/BF02579196.
• N. Alon, M. Krivelevich e B. Sudakov, <457::AID-RSA14>3.0.CO;2-W Finding a large hidden clique in a random graph, in Random Structures & Algorithms, vol. 13, 3–4, 1998, 457–466, DOI:10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W.
• N. Alon, R. Yuster e U. Zwick, Finding and counting given length cycles, in Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands, 1994, 354–364.
• K. Amano e A. Maruoka, A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log log n negation gates, in Proc. Symp. Mathematical Foundations of Computer Science^{[collegamento interrotto]}, Lecture Notes in Computer Science, vol. 1450, Springer-Verlag, 1998, 399–408.
• Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan e Mario Szegedy, Proof verification and the hardness of approximation problems, in Rivista of the ACM, vol. 45, n. 3, 1998, 501–555, DOI:10.1109/SFCS.1992.267823, ECCC TR98-008.. Presentato originariamente al Symposium on Foundations of Computer Science del 1992
• S. Arora e S. Safra, Probabilistic checking of proofs: A new characterization of NP, in Rivista of the ACM, vol. 45, n. 1, 1998, 70–122, DOI:10.1109/SFCS.1992.267824, presentato originariamente al Symposium on Foundations of Computer Science del 1992,.
• E. Balas e C. S. Yu, Finding a maximum clique in an arbitrary graph, in SIAM Rivista on Computing, vol. 15, n. 4, 1986, 1054–1068, DOI:10.1137/0215075.
• R. Battiti e M. Protasi, Reactive local search for the maximum clique problem, in Algorithmica, vol. 29, n. 4, 2001, 610–637, DOI:10.1007/s004530010074.
• Béla Bollobás, Complete subgraphs are elusive, in Rivista of Combinatorial Theory, Serie B, vol. 21, n. 1, 1976, 1–7, DOI:10.1016/0095-8956(76)90021-6, ISSN 0095-8956 (WC · ACNP).
• I. M. Bomze, M. Budinich, P. M. Pardalos e M. Pelillo, The maximum clique problem, in Handbook of Combinatorial Optimization, vol. 4, Kluwer Academic Editores, 1999, 1–74, CiteSeerX: 10.1.1.48.4074.
• R. Boppana e M. M. Halldórsson, Approximating maximum independent sets by excluding subgraphs, in BIT, vol. 32, n. 2, 1992, 180–196, DOI:10.1007/BF01994876.
• C. Bron e J. Kerbosch, Algorithm 457: finding all cliques of an undirected graph, in Communications of the ACM, vol. 16, n. 9, 1973, 575–577, DOI:10.1145/362342.362367.
• R. Carraghan e P. M. Pardalos, An exact algorithm for the maximum clique problem (PDF), in Operations Research Letters, vol. 9, n. 6, 1990, 375–382, DOI:10.1016/0167-6377(90)90057-C (archiviato dall'url originale il 17 luglio 2011).
• F. Cazals e C. Karande, A note on the problem of reporting maximal cliques (PDF) ^{[collegamento interrotto]}, in Theoretical Computer Science, vol. 407, n. 1, 2008, 564–568, DOI:10.1016/j.tcs.2008.05.010.
• Jianer Chen, Xiuzhen Huang, Iyad A. Kanj e Ge Xia, Strong computational lower bounds via parameterized complexity, in J. Comput. Syst. Sci., vol. 72, n. 8, 2006, 1346–1367, DOI:10.1016/j.jcss.2006.04.007.
• N. Chiba e T. Nishizeki, Arboricity and subgraph listing algorithms, in SIAM Rivista on Computing, vol. 14, n. 1, 1985, 210–223, DOI:10.1137/0214017.
• A. M. Childs, E. Farhi, J. Goldstone e S. Gutmann, Finding cliques by quantum adiabatic evolution, in Quantum Information and Computation, vol. 2, n. 3, 2002, 181–191, arXiv:quant-ph/0012104.
• A. M. Childs e J. M. Eisenberg, Quantum algorithms for subset finding, in Quantum Information and computation, vol. 5, n. 7, 2005, 593–604, arXiv:quant-ph/0311038.
• Brent N. Clark, Charles J. Colbourn e David S. Johnson, Unit disk graphs, in Discrete Mathematics, vol. 86, 1–3, 1990, 165–177, DOI:10.1016/0012-365X(90)90358-O.
• S. A. Cook, The complexity of theorem-proving procedures, in Symposium on Theory of Computing, 1971, 151–158, DOI:10.1145/800157.805047.
• R. G. Downey e M. R. Fellows, Fixed-parameter tractability and completeness. II. On completeness for W[1], in Theoretical Computer Science, vol. 141, 1–2, 1995, 109–131, DOI:10.1016/0304-3975(94)00097-3.
• R. G. Downey e M. R. Fellows, Parameterized complexity, Springer-Verlag, 1999, ISBN 0-387-94883-X.
• F. Eisenbrand e F. Grandoni, On the complexity of fixed parameter clique and dominating set, in Theoretical Computer Science, vol. 326, 1–3, 2004, 57–67, DOI:10.1016/j.tcs.2004.05.009.
• David Eppstein, Maarten Löffler e Darren Strash, Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time, in Otfried Cheong, Kyung-Yong Chwa e Kunsoo Park (a cura di), 21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea, Lecture Notes in Computer Science, vol. 6506, Springer-Verlag, 2010, 403–414, DOI:10.1007/978-3-642-17517-6_36, ISBN 978-3-642-17516-9, arXiv:1006.5440.
• David Eppstein e Darren Strash, Listing all maximal cliques in large sparse real-world graphs, in 10th International Symposium on Experimental Algorithms, 2011, arXiv:1103.0318.
• Paul Erdős e George Szekeres, A combinatorial problem in geometry (PDF), in Compositio Mathematica, vol. 2, 1935, 463–470.
• S. Even, A. Pnueli e A. Lempel, Permutation graphs and transitive graphs, in Rivista of the ACM, vol. 19, n. 3, 1972, 400–410, DOI:10.1145/321707.321710.
• T. Fahle, Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique, in Proc. 10th European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 2461, Springer-Verlag, 2002, 47–86, DOI:10.1007/3-540-45749-6_44, ISBN 978-3-540-44180-9.
• U. Feige, Approximating maximum clique by removing subgraphs, in SIAM Rivista on Discrete Mathematics, vol. 18, n. 2, 2004, 219–225, DOI:10.1137/S089548010240415X.
• U. Feige, S. Goldwasser, L. Lovász, S Safra e M. Szegedy, Approximating clique is almost NP-complete, in Proc. 32nd IEEE Symp. on Foundations of Computer Science, 1991, 2–12, DOI:10.1109/SFCS.1991.185341, ISBN 0-8186-2445-0.
• U. Feige e R. Krauthgamer, <195::AID-RSA5>3.0.CO;2-A Finding and certifying a large hidden clique in a semirandom graph, in Random Structures and Algorithms, vol. 16, n. 2, 2000, 195–208, DOI:10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A.
• M. R. Garey e D. S. Johnson, "Strong" NP-completeness results: motivation, examples and implications, in Rivista of the ACM, vol. 25, n. 3, 1978, 499–508, DOI:10.1145/322077.322090.
• F. Gavril, Algorithms for a maximum clique and a maximum independent set of a circle graph, in Networks, vol. 3, n. 3, 1973, 261–273, DOI:10.1002/net.3230030305.
• M. Goldmann e J. Håstad, A simple lower bound for monotone clique using a communication game, in Information Processing Letters, vol. 41, n. 4, 1992, 221–226, DOI:10.1016/0020-0190(92)90184-W.
• M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Computer Science and Applied Mathematics, Academic Press, 1980, ISBN 0-444-51530-5.
• Hans Dietmar Gröger, On the randomized complexity of monotone graph properties (PDF), in Acta Cybernetica, vol. 10, n. 3, 1992, 119–127. URL consultato il 10 febbraio 2009 (archiviato dall'url originale il 24 settembre 2015).
• A. Grosso, M. Locatelli e F. Della Croce, Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem, in Rivista of Heuristics, vol. 10, n. 2, 2004, 135–152, DOI:10.1023/B:HEUR.0000026264.51747.7f.
• M. Grötschel, L. Lovász e A. Schrijver, 9.4 Coloring Perfect Graphs, in Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2, Springer–Verlag, 1988, 296–298, ISBN 0-387-13624-X.
• G. Gutin, 5.3 Independent sets and cliques, in J. L. Gross e J. Yellen (a cura di), Handbook of graph theory, Discrete Mathematics & Its Applications, CRC Press, 2004, 389–402, ISBN 978-1-58488-090-5.
• M. M. Halldórsson, Approximations of Weighted Independent Set and Hereditary Subset Problems (PDF), in Rivista of Graph Algorithms and Applications, vol. 4, n. 1, 2000, 1–16.
• F. Harary e I. C. Ross, A procedure for clique detection using the group matrix, in Sociometry, vol. 20, n. 3, American Sociological Association, 1957, 205–215, DOI:10.2307/2785673, JSTOR 2785673, MR 0110590.
• J. Håstad, Clique is hard to approximate within n^1 − ε, in Acta Mathematica, vol. 182, n. 1, 1999, 105–142, DOI:10.1007/BF02392825.
• R. Impagliazzo, R. Paturi e F. Zane, Which problems have strongly exponential complexity?, in Rivista of Computer and System Sciences, vol. 63, n. 4, 2001, 512–530, DOI:10.1006/jcss.2001.1774.
• A. Itai e M. Rodeh, Finding a minimum circuit in a graph, in SIAM Rivista on Computing, vol. 7, n. 4, 1978, 413–423, DOI:10.1137/0207033.
• M. Jerrum, Large cliques elude the Metropolis process, in Random Structures and Algorithms, vol. 3, n. 4, 1992, 347–359, DOI:10.1002/rsa.3240030402.
• T Jian, An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem, in IEEE Transactions on Computers, vol. 35, n. 9, IEEE Computer Society, 1986, 847–851, DOI:10.1109/TC.1986.1676847, ISSN 0018-9340 (WC · ACNP).
• D. S. Johnson e M. A. Trick (a cura di), Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993, DIMACS Serie in Discrete Mathematics and Theoretical Computer Science, vol. 26, American Mathematical Society, 1996, ISBN 0-8218-6609-5.
• D. S. Johnson e M. Yannakakis, On generating all maximal independent sets, in Information Processing Letters, vol. 27, n. 3, 1988, 119–123, DOI:10.1016/0020-0190(88)90065-8.
• Richard M. Karp, Reducibility among combinatorial problems (PDF), in R. E. Miller e J. W. Thatcher (a cura di), Complexity of Computer Computations, New York, Plenum, 1972, 85–103. URL consultato il 3 maggio 2019 (archiviato dall'url originale il 4 marzo 2016).
• Richard M. Karp, Probabilistic analysis of some combinatorial search problems, in J. F. Traub (a cura di), Algorithms and Complexity: New Directions and Recent Results, New York, Academic Press, 1976, 1–19.
• K. Katayama, A. Hamamoto e H. Narihisa, An effective local search for the maximum clique problem, in Information Processing Letters, vol. 95, n. 5, 2005, 503–511, DOI:10.1016/j.ipl.2005.05.010.
• S. Khot, Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring, in Proc. 42nd IEEE Symp. Foundations of Computer Science, 2001, 600–609, DOI:10.1109/SFCS.2001.959936, ISBN 0-7695-1116-3.
• T. Kloks, D. Kratsch e H. Müller, Finding and counting small induced subgraphs efficiently, in Information Processing Letters, vol. 74, 3–4, 2000, 115–121, DOI:10.1016/S0020-0190(00)00047-8.
• J. Konc e D. Janežič, An improved branch and bound algorithm for the maximum clique problem (PDF), in MATCH Communications in Mathematical and in Computer Chemistry, vol. 58, n. 3, 2007, 569–590. URL consultato il 26 marzo 2014 (archiviato dall'url originale il 27 marzo 2014). Source code
• R. J. Lipton e R. E. Tarjan, Applications of a planar separator theorem, in SIAM Rivista on Computing, vol. 9, n. 3, 1980, 615–627, DOI:10.1137/0209046.
• R. Duncan Luce e Albert D. Perry, A method of matrix analysis of group structure, in Psychometrika, vol. 14, n. 2, 1949, 95–116, DOI:10.1007/BF02289146, PMID 18152948.
• Frédéric Magniez, Miklos Santha e Mario Szegedy, Quantum algorithms for the triangle problem, in SIAM Rivista on Computing, vol. 37, n. 2, 2007, 413–424, DOI:10.1137/050643684, arXiv:quant-ph/0310134.
• K. Makino e T. Uno, New algorithms for enumerating all maximal cliques, in Algorithm Theory: SWAT 2004^{[collegamento interrotto]}, Lecture Notes in Computer Science, vol. 3111, Springer-Verlag, 2004, 260–272.
• J. W. Moon e L. Moser, On cliques in graphs, in Israel Rivista of Mathematics, vol. 3, 1965, 23–28, DOI:10.1007/BF02760024, MR 0182577.
• J. Nešetřil e S. Poljak, On the complexity of the subgraph problem, in Commentationes Mathematicae Universitatis Carolinae, vol. 26, n. 2, 1985, 415–419.
• P. R. J. Östergård, A fast algorithm for the maximum clique problem, in Discrete Applied Mathematics, vol. 120, 1–3, 2002, 197–207, DOI:10.1016/S0166-218X(01)00290-6.
• Q. Ouyang, P. D. Kaplan, S. Liu e A. Libchaber, DNA solution of the maximal clique problem, in Science, vol. 278, n. 5337, 1997, 446–449, DOI:10.1126/science.278.5337.446, PMID 9334300.
• P. M. Pardalos e G. P. Rogers, A branch and bound algorithm for the maximum clique problem, in Computers & Operations Research, vol. 19, n. 5, 1992, 363–375, DOI:10.1016/0305-0548(92)90067-F.
• (RU) A. A. Razborov, Lower bounds for the monotone complexity of some Boolean functions, in Proceedings of the USSR Academy of Sciences, vol. 281, 1985, 798–801.
• J.-C. Régin, Using constraint programming to solve the maximum clique problem, in Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003^{[collegamento interrotto]}, Lecture Notes in Computer Science, vol. 2833, Springer-Verlag, 2003, 634–648.
• J. M. Robson, Algorithms for maximum independent sets, in Rivista of Algorithms, vol. 7, n. 3, 1986, 425–440, DOI:10.1016/0196-6774(86)90032-5.
• J. M. Robson, Finding a maximum independent set in time O(2^n/4), 2001.
• B Rosgen e L Stewart, Complexity results on graphs with few cliques, in Discrete Mathematics and Theoretical Computer Science, vol. 9, n. 1, 2007, 127–136 (archiviato dall'url originale il 23 settembre 2015).
• M. Sipser, Introduction to the Theory of Computation, International Thompson Publishing, 1996, ISBN 0-534-94728-X.
• R. E. Tarjan e A. E. Trojanowski, Finding a maximum independent set (PDF) ^{[collegamento interrotto]}, in SIAM Rivista on Computing, vol. 6, n. 3, 1977, 537–546, DOI:10.1137/0206038.
• E. Tomita e T. Kameda, An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments, in Rivista of Global Optimization, vol. 37, n. 1, 2007, 95–111, DOI:10.1007/s10898-006-9039-7.
• E. Tomita e T. Seki, An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique, in Discrete Mathematics and Theoretical Computer Science, Lecture Notes in Computer Science, vol. 2731, Springer-Verlag, 2003, 278–289, DOI:10.1007/3-540-45066-1_22, ISBN 978-3-540-40505-4.
• E. Tomita, A. Tanaka e H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, in Theoretical Computer Science, vol. 363, n. 1, 2006, 28–42, DOI:10.1016/j.tcs.2006.06.015.
• S. Tsukiyama, M. Ide, I. Ariyoshi e I. Shirakawa, A new algorithm for generating all the maximal independent sets, in SIAM Rivista on Computing, vol. 6, n. 3, 1977, 505–517, DOI:10.1137/0206036.
• L. G. Valiant, Exponential lower bounds for restricted monotone circuits, in Proc. 15th ACM Symposium on Theory of Computing, 1983, 110–117, DOI:10.1145/800061.808739, ISBN 0-89791-099-0.
• V. Vassilevska e R. Williams, Finding, minimizing, and counting weighted subgraphs, in Proc. 41st ACM Symposium on Theory of Computing, 2009, 455–464, DOI:10.1145/1536414.1536477, ISBN 978-1-60558-506-2.
• I. Wegener, On the complexity of branching programs and decision trees for clique functions, in Rivista of the ACM, vol. 35, n. 2, 1988, 461–472, DOI:10.1145/42282.46161.
• R. Yuster, Finding and counting cliques and independent sets in r-uniform hypergraphs, in Information Processing Letters, vol. 99, n. 4, 2006, 130–134, DOI:10.1016/j.ipl.2006.04.005.
• D. Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, in Proc. 38th ACM Symp. Theory of Computing, 2006, 681–690, DOI:10.1145/1132516.1132612, ISBN 1-59593-134-1, ECCC TR05-100.

Portale Informatica

Portale Matematica