Problema della cricca: differenze tra le versioni

Versione delle 22:10, 5 apr 2014

Versione attuale delle 14:19, 15 ott 2025

(46 versioni intermedie di 22 utenti non mostrate)

Riga 1:

[[File:Brute force Clique algorithm.svg|thumb|240px|L'[[Metodo forza bruta|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 [[Combinazione|C]](7,4)=35 per verificare la completezza.]]

In [[informatica]], il '''problema della cricca''' si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari [[Glossario di teoria dei grafi#Sottografo|sottografi]] [[Grafo completo|completi]] ("[[Cricca (teoria dei grafi)|cricche]]") in un [[grafo]], cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa.

Riga 6:

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 ponderatopesato]],

* elencare tutte le [[Cricca massimale|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 [[Complessità parametrizzata|intrattabile a parametro fisso]], sia [[Difficoltà di approssimazione|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.<ref name="bbpp">Per una rassegna di questi algoritmi di questi algoritmi e per le definizioni di base usate in questo articolo, vedi {{cita|Bomze1999||Bomze, Budinich, Pardalos & Pelillo (1999)|harv=s|Bomze1999}} e {{cita|Gutin2004||Gutin (2004)|harv=s|Gutin2004}}.</ref>

== Storia ==

Sebbene i sottografi completi siano studiati da più tempo in matematica,<ref>I sottografi completi fanno una prima apparizione nella letteratura matematica nella riformulazione della teoria dei grafi della [[teoria di Ramsey]] da parte di {{cita|Erdős1935||Erdős & Szekeres (1935)|harv=s|Erdős1935}}.</ref> il termine "cricca" (''clique'' nell'originale [[Lingua inglese|inglese]]) e il problema di elencare algoritmicamente le cricche vengono entrambi dalle [[scienze sociali]], dove i sottografi completi sono usati per modellare le [[Cricca|cricche sociali]], gruppi di persone che si conoscono tutte fra di loro. La terminologia della "cricca" viene da {{cita|Luce1949||Luce & Perry (1949)|harv=s|Luce1949}}, e il primo algoritmo per risolvere il problema della cricca è quello di {{cita|Harary1957||Harari & Ross (1957)|harv=s|Harary1957}},<ref name="bbpp"/> 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.<ref name="bbpp"/> Negli anni 1970, i ricercatori cominciarono a studiare questi algoritmi dal punto di vista dell'[[analisi del caso peggiore]]; vedi, per esempio, {{cita|Tarjan1977||Tarjan & Trojanowski (1977)|harv=s|Tarjan1977}}, un primo lavoro sulla complessità del caso peggiore nel problema della cricca massima. Sempre negli anni 1970, a cominciare dal lavoro di {{cita|Cook1971||Cook (1971)|harv=s|Cook1971}} e {{cita|Karp1972||Karp (1972)|harv=s|Karp1972}}, i ricercatori iniziarono a trovare giustificazioni matematiche per la difficoltà percepita del problema della cricca nella teoria della [[NP-completo|NP-completezza]] e dei risultati correlati sull'intrattabilità. Negli anni 1990, una serie di studi rivoluzionari iniziati con {{cita|Feige1991||Feige et al. (1991)|harv=s|Feige1991}} e riportati all'epoca dai principali giornali,<ref name="nyt">{{cita testo |titolo=In a Frenzy, Math Enters Age of Electronic Mail |nome=Gina |cognome=Kolata |rivista=[[New York Times]] |url=httphttps://www.nytimes.com/1990/06/26/science/in-a-frenzy-math-enters-age-of-electronic-mail.html |data=26 giugno 1990}}</ref> mostrarono che non è neanche possibile approssimare il problema in modo accurato ed efficiente.

== Definizioni ==

{{vedi anche|Cricca (teoria dei grafi)}}

[[File:6n-graf-clique.svg|thumb|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 [[Vertice (teoria dei grafi)|vertici]] e da un insieme di [[Coppia non ordinata|coppie non ordinate]] di vertici, che sono chiamati [[Spigolo (teoria dei grafi)|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 (teoria dei grafi)|cricca]] in un grafo ''G'' è un [[Glossario di teoria dei grafi#Sottografo|sottografo]] [[Grafo completo|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''.<ref name="bbpp"/>

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 di verità|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-completo|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 [[Grafo planare|grafi planari]],<ref name="CN85">{{cita|Chiba1985||Chiba & Nishizeki (1985)|harv=s|Chiba1985}}.</ref> mentre il problema dell'insieme indipendente rimane NP-difficile sui grafi planari.

== Algoritmi ==

=== Massimale contro massima ===

Una cricca [[Elemento massimale|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.

Riga 40:

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 [[Metodo forza bruta|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''&nbsp;''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.<ref>Ad es., vedi {{cita|Downey1995||Downey & Fellows (1995)|harv=s|Downey1995}}.</ref>

Il più semplice caso non banale del problema di trovare una cricca è trovare un triangolo in un grafo, o in modo equivalenteequivalentemente di determinare se il grafo è [[Grafo senza triangoli|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.<ref>{{cita|Itai1978||Itai & Rodeh (1978)|harv=s|Itai1978}} 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; {{cita|Chiba1985||Chiba & Nishizeki (1985)|harv=s|Chiba1985}} elencano tutti i triangoli nel tempo O(''m''^3/2).</ref> Per esempio, {{cita|Chiba1985||Chiba & Nishizeki (1985)|harv=s|Chiba1985}} 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''&nbsp;''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''&nbsp;&minus;&nbsp;2)-esima potenza dell'arboricità.<ref name="CN85"/> 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 {{cita|Itai1978||Itai & Rodeh (1978)|harv=s|Itai1978}}, 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 [[Don Coppersmith|Coppersmith]]-[[Schmuel Winograd|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 [[Grafo denso|grafi sufficientemente densi]]. {{cita|Alone1994||Alon, Yuster & Zwick (1994)|harv=s|Alone1994}} 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''.<ref>{{cita|Eisenbrand2004|Eisenbrand & Grandoni (2004)|harv=s}}; {{cita|Kloks2000||Kloks, Kratsch & Müller (2000)|harv=s|Kloks2000}}; {{cita|Nešetřil1985||Nešetřil & Poljak (1985)|harv=s|Nešetřil1985}}; {{cita|Vassilevska2009||Vassilevska & Williams (2009)|harv=s|Vassilevska2009}}; {{cita|Yuster2006||Yuster (2006)|harv=s|Yuster2006}}.</ref>

=== Elencare tutte le cricche massimali ===

Secondo un risultato di {{cita|Moon1965||Moon & Moser (1965)|harv=s|Moon1965}}, qualsiasi grafo con ''n'' vertici ha al più 3^''n''/3 cricche massimali. L'[[algoritmo di Bron-Kerbosch]] è una procedura ricorsiva di [[Backtracking|ritorno all'indietro]] (''backtracking'') di {{cita|Bron1973||Bron & Kerbosch (1973)|harv=s|Bron1973}} 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).<ref>{{cita|Tomita2006||Tomita, Tanaka & Takahashi (2006)|harv=s|Tomita2006}}.</ref> 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 èstato ampiamente riportato essereè in pratica più veloce delle sue alternative.<ref>{{cita|Cazals2008||Cazals & Karande (2008)|harv=s|Cazals2008}}; {{cita|Eppstein2011||Eppstein & Strash (2011)|harv=s|Eppstein2011}}.</ref>

Come mostrarono {{cita|Tsukiyama1977||Tsukiyama, Ide, Ariyoshi & Shirakawa (1977)|harv=s|Tsukiyama1977}}, è 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''&nbsp;\&nbsp;''v'' formato rimuovendo un vertice arbitrario ''v'' da ''G'':

* Per ogni cricca massimale ''C'' ddi ''G''&nbsp;\&nbsp;''v'', o ''C'' continua a formare una cricca massimale in ''G'', o ''C''&nbsp;⋃&nbsp;{v} forma una cricca massimale in ''G''. Perciò, ''G'' ha almeno altrettante cricche massimali di ''G''&nbsp;\&nbsp;''v''.

* Ciascuna cricca massimale in ''G'' che non contenga ''v'' è una cricca massimale in ''G''&nbsp;\&nbsp;''v'', e ciascuna cricca massimale in ''G'' che non contiene ''v'' può essere formata da una cricca massimale ''C'' in ''G''&nbsp;\&nbsp;''v'' aggiungendo ''v'' e rimuovendo i non vicini di ''v'' da ''C''.

Usando queste osservazioni esse possono generare tutte le cricche nassimalimassimali in ''G'' mediante un [[algoritmo ricorsivo]] che, per ciascuna cricca massimale ''C'' in ''G''&nbsp;\&nbsp;''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''&nbsp;\&nbsp;''v'', così eliminano i duplicati producendo come uscita una cricca in ''G'' solo quando la sua genitrice in ''G''&nbsp;\&nbsp;''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; {{cita|Chiba1985||Chiba & Nishizeki (1985)|harv=s|Chiba1985}} migliorano questo valore a O(''ma'') per ogni cricca, dove ''a'' è l'[[arboricità]] del grafo dato. {{cita|Makino2004||Makino & Uno (2004)|harv=s|Makino2004}} forniscono un algoritmo alternativo sensibile all'uscita basato sulla moltiplicazione veloce tra matrici, e {{cita|Johnson2004||Johnson & Yannakakis (1988)|harv=s|Johnson2004}} 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 [[Grafo cordale|grafi cordali]], i [[Grafo completo|grafi completi]], i [[Grafo senza triangoli|grafi senza triangoli]], i [[Grafo d'intervallo|grafi d'intervallo]], i grafi di [[bossicità]] limitata e i [[Grafo planare|grafi planari]].<ref>{{cita|Rosgen2007||Rosgen & Stewart (2007)|harv=s|Rosgen2007}}.</ref> In particolare, i grafi planari e, più generalmente, qualsiasi famiglia di grafi che è sia [[Grafo denso|sparsa]] (avendo uncome numero di spigoli al massimo una costante per il numero di vertici), sia [[Proprietà di chiusura|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.<ref name="CN85"/><ref name="ELS10">{{cita|Eppstein2010||Eppstein, Löffler & Strash (2010)|harv=s|Eppstein2010}}.</ref>

=== 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^''n'') 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 {{cita|Tarjan1977||Tarjan & Trojanowski (1977)|harv=s|Tarjan1977}} risolve questo problema nel tempo O(2^''n''/3) = O(1,2599^''n''); è 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. {{cita|Jian1986||Jian (1986)|harv=s|Jian1986}} migliorò questo in O(2^0,304''n'') = O(1,2346^''n''). {{cita|Robson1986||Robson (1986)|harv=s|Robson1986}} lo migliorò nel tempo O(2^0,276''n'') = O(1,2108^''n''), 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 {{cita|Robson2001||Robson (2001)|harv=s|Robson2001}}, che si esegue nel tempo O(2^0,249''n'') = O(1,1888^''n'').

Ci sono state estese ricerche anche su [[Algoritmo euristico|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]]'',<ref>{{cita|Balas1986||Balas & Yu (1986)|harv=s|Balas1986}}; {{cita|Carraghan1990||Carraghan & Pardalos (1990)|harv=s|Carraghan1990}}; {{cita|Pardalos1992||Pardalos & Rogers (1992)|harv=s|Pardalos1992}}; {{cita|Östergård2002||Östergård (2002)|harv=s|Östergård2002}}; {{cita|Fahle2002||Fahle (2002)|harv=s|Fahle2002}}; {{cita|Tomita2003||Tomita & Seki (2003)|harv=s|Tomita2003}}; {{cita|Tomita2007||Tomita & Kameda(2007)|harv=s|Tomita2007}}; {{cita|Konc2007||Konc & Janežič (2007)|harv=s|Konc2007|}}.</ref> la [[Ricerca locale (ottimizzazione)|ricerca locale]],<ref>{{cita|Battiti2001||Battiti & Protasi (2001)|harv=s|Battiti2001}}; {{cita|Katayama2005||Katayama, Hamamoto & Narihisa (2005)|harv=s|Katayama2005}}.</ref> gli [[Algoritmo greedy|algoritmi golosi]],<ref>{{cita|Abello1999||Abello, Pardalos & Resende (1999)|harv=s|Abello1999}}; {{cita|Grosso2004||Grosso, Locatelli & Della Croce (2004)|harv=s|Grosso2004}}.</ref> e la [[programmazione a vincoli]].<ref>{{cita|Régin2003||Régin (2003)|harv=s|Régin2003}}.</ref> Le metodologie di computazione non standard per trovare le cricche includono la [[computer a DNA|computazione a DNA]]<ref>{{cita|Ouyang1997||Ouyang et al. (1997)|harv=s|Ouyang1997}}. Sebbene il titolo si riferisca alle cricche massimali, il problema che questo saggio risolve è in effetti il problema della cricca massima.</ref> e la [[computazione quantistica adiabatica]].<ref>{{cita|Childs2002||Childs et al. (2002)|harv=s|Childs2002}}.</ref> Il problema della cricca massima era l'argomento di una sfida di implementazione sponsorizzato dal [[DIMACS]] nel 1992–1993,<ref>{{cita|Johnson1996||Johnson & Trick (1996)|harv=s|Johnson1996}}.</ref> e una collezione di grafi usati come parametri di riferimento per, la sfida è disponibile pubblicamente.<ref>[ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/ ''DIMACS challenge graphs for the clique problem''] {{webarchive|url=http://archive.wikiwix.com/cache/20091218033633/ftp://dimacs.rutgers.edu/pub/challenge/graph/benchmarks/clique/ |data=18 dicembre 2009 }}, consultato il 17-12-2009.</ref>

=== Classi speciali di grafi ===

[[File:Permutation graph.svg|thumb|In questo [[grafo di permutazione]], le cricche massime corrispondono alle [[Sottosequenza crescente più lunga|sottosequenze decrescenti più lunghe]] (4,3,1) e (4,3,2) della permutazione definita.]]

I [[Grafo planare|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.<ref name="CN85"/> In particolare, per i grafi planari, qualsiasi cricca può avere al massimo quattro vertici, in base al [[teorema di Kuratowski]].

I [[Grafo perfetto|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 [[Sottografo indotto|sottografi indotti]]. Per i grafi perfetti, è possibile trovare una cricca massima in tempo polinomiale, usando un algoritmo basato sulla [[programmazione semidefinita]].<ref>{{cita|Grötschel1988||Grötsche, Lovász & Schrijver (1988)|harv=s|Grötschel1988}}.</ref>

Tuttavia, questo metodo è complesso e non combinatorio, e algoritmi specializzati per la ricerca di cricche sono stati sviluppati per molte sottoclassi di grafi perfetti.<ref>{{cita|Golumbic1980||Golumbic (1980)|harv=s|Golumbic1980}}.</ref> Nei [[Grafo complemento|grafi complemento]] dei [[Grafo bipartito|grafi bipartiti]], il [[Teorema di König (teoria dei grafi)|teorema di König]] permette al problema della cricca massima di essere risolto usando tecniche per l'[[Accoppiamento (teoria dei grafi)|accoppiamento]]. In un'altra classe di grafi perfetti, i [[Grafo di permutazione|grafi di permutazione]], una cricca massima è una [[Sottosequenza crescente più lunga|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.<ref>{{cita|Golumbic1980||Golumbic (1980)|harv=s|Golumbic1980}}, p. 159. {{cita|Even1972||Ecen, Pnueli & Lempel (1972)|harv=s|Even1972}} forniscono un algoritmo alternativo in tempo quadratico per le cricche massime nei [[Grafo di comparabilità|grafi di comparabilità]], una classe di grafi perfetti più vasta che include i grafi di permutazione come caso speciale.</ref> Nei [[Grafo cordale|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 (teoria dei grafi)|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.<ref>{{cita|Gavril1973||Gavril (1973)|harv=s|Gavril1973}}; {{cita|Golumbic1980||Golumbic (1980)|harv=s|Golumbic1980}}, p. 247.</ref> 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.<ref>{{cita|Clark1990||Clark, Colbourn & Johnson (1990)|harv=s|Clark1990}}.</ref>

Il problema algoritmico di trovare una cricca massmamassima 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 {{cita|Karp1976||Karp (1976)|harv=s|Karp1976}}. Sebbene il numero di cricca di tali grafi sia molto vicino a 2&nbsp;log₂''n'', semplici [[Algoritmo greedy|algoritmi golosi]] come pure più sofisticate tecniche di approssimazione randomizzate<ref>{{cita|Jerrum1992||Jerrum (1992)|harv=s|Jerrum1992}}.</ref> 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 [[Teoria spettrale dei grafi|metodi spettrali]]<ref>{{cita|Alon1998||Alon, Krivelevich & Sudakov (1998)|harv=s|Alon1998}}.</ref> o la [[programmazione semidefinita]].<ref>{{cita|Feige2000||Feige & Krauthgamer (2000)|harv=s|Feige2000}}.</ref>

=== Algoritmi di approssimazione ===

Parecchi autori hanno considerato [[Algoritmo di approssimazione|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à.<ref>{{cita|Boppana1992||Boppana & Halldórsson (1992)|harv=s|Boppana1992}}; {{cita|Feige2004||Feige (2004)|harv=s|Feige2004}}; {{cita|Haldórsson2000||Halldórsson (2000)|harv=s|Haldórsson2000}}.</ref>

{{cita|Feige2004||Feige (2004)|harv=s|Feige2004}} descrive un algoritmo in tempo polinomiale che trova una cricca di dimensione Ω((log&nbsp;''n''/log&nbsp;log&nbsp;''n'')²) in qualsiasi grafo che abbia numero di cricca Ω(''n''/log^''k''''n'') per qualsiasi costante ''k''. Combinando questo algoritmo per trovare cricche in grafi con numeri di cricca tra ''n''/log&nbsp;''n'' e ''n''/log³''n'' con un diverso algoritmo di {{cita|Boppana1992||Boppana & Halldórsson (1992)|harv=s|Boppana1992}} 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, [[Uriel Feige|Feige]] fornisce un algoritmo di approssimazione che trova una cricca con un numero di vertici entro un fattore di O(''n''(log&nbsp;log&nbsp;''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 ===

[[File:Sat reduced to Clique from Sipser.svg|thumb|L'istanza di soddisfacibilità 3-CNF (x&#x202F;∨&#x202F;x&#x202F;∨&#x202F;y) ∧ (~x&#x202F;∨&#x202F;~y&#x202F;∨&#x202F;~y) ∧ (~x&#x202F;∨&#x202F;y&#x202F;∨&#x202F;y) ridotta a cricca. I vertici verdi formano una 3-cricca e corrispondono a un'assegnazione soddisfacente.<ref>Adattato da {{cita|Sipser1996||Sipser (1996)|harv=s}}.</ref>]]

Il problema decisionale della cricca è [[NP-completo]]. Era uno dei [[21 problemi NP-completi di Karp|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]].<ref>{{cita|Cook1971||Cook (1971)|harv=s|Cook1971}} dà essenzialmente la stessa riduzione, da [[3-SAT]] invece della soddisfacibilità, per mostrare che l'[[isomorfismo di sottografi]] è NP-completo.</ref> 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''&nbsp;≠&nbsp;''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 [[Valore di verità|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 [[Grafo planare|grafi planari]]) possono essere risolti in un tempo che è esponenziale in una funzione sublineare del parametro ''n'' della dimensione dell'entrata.<ref>{{cita|Lipton1980||Lipton & Tarjan (1980)|harv=s|Lipton1980}}.</ref>

Tuttavia, come descrivono {{cita|Impagliazzo2001||Impagliazzo, Paturi & Zane (2001)|harv=s|Impagliazzo2001}}, è 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 ===

[[File:Monotone circuit for 3-clique.svg|thumb|Un circuito monotono per riolevarerilevare una ''k''-cricca in un grafo a ''n'' vertici per ''k''&nbsp;=&nbsp;3 ed ''n''&nbsp;=&nbsp;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 ogmiogni 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à ereditaria|proprietà monotona dei grafi]] (se esiste una cricca in un dato grafo, esisterà in qualsiasi supergrafo), deve esistere un circuito monotono, che usa solo [[Porta AND|porte AND]] e [[Porta OR|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.<ref>{{cita|Alon1987||Alon & Boppana (1987)|harv=s|Alon1987}}. Per limiti anteriori e più deboli sul problema della cricca, vedi {{cita|Valiant1983||Valiant (1983)|harv=s|Valiant1983}} e {{cita|Razborov1985||Razborov (1985)|harv=s|Razborov1985}}.</ref> Anche se sono ammesse un piccolo numero di [[Porta NOT|porte NOT]], la complessità rimane superpolinomiale.<ref>{{cita|Amano1998|Amano & Maruoka (1998)|harv=s}}.</ref> 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.<ref>{{cita|Goldmann1992||Goldmann & Håstad (1992)|harv=s|Goldmann1992}} usarono la [[complessità della comunicazione]] per dimostrare questo risultato.</ref>

=== Complessità degli alberi decisionali ===

[[File:Decision tree for 3-clique no arrowheads.svg|thumb|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''&nbsp;&minus;&nbsp;1)/2.]]

La complessità (deterministica) dell'[[Modello dell'albero decisionale|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 [[Modello dell'albero decisionale|albero decisionale]] booleano per il problema. Dal momento che ci sono al massimo ''n''(''n''&nbsp;&minus;&nbsp;1)/2 domande possibili a cui rispondere, qualsiasi proprietà dei grafi può essere determinata con ''n''(''n''&nbsp;&minus;&nbsp;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''&nbsp;&minus;&nbsp;1)/2. Per gli alberi decisionali deterministici, fu dimostrato da {{cita|Bollobás1976||Bollobás (1976)|harv=s|Bollobás1976}} che una ''k''-cricca (2 ≤ ''k'' ≤ ''n'') ha una complessità degli alberi esattamente di ''n''(''n''&nbsp;&minus;&nbsp;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.<ref>{{cita|Wegener1988||Wegener (1988)|harv=s|Wegener1988}}.</ref>

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²).<ref>Per esempio, questo consegue da {{cita|Gröger1992||Gröger (1992)|harv=s|Gröger1992}}.</ref> Per gli alberi decisionali quantici, il limite inferiore più noto è Ω(n), ma non si conosce nessun algoritmo corrispondente per il caso di ''k'' ≥ 3.<ref>{{cita|Childs2005||Childs & Eisenberg (2005)|harv=s|Childs2005}}; {{cita|Magniez2007||Magniez, Santha & Szegedy (2007)|harv=s|Magniez2007}}.</ref>

=== Intrattabilità a parametro fisso ===

La [[complessità parametrizzata]]<ref>{{cita|Downey1999||Downey & Fellows (1999)|harv=s|Downey1999}}.</ref> è lo studio di [[Teoria della complessità computazionale|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'')&nbsp;''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 dioendedipende da ''k''.

Per il problema della cricca, l'algoritmo di forza bruta ha un tempo di esecuzione O(''n''^''k''''k''²), e sebbene possa essere miglioraromigliorato dalla moltiplicazione delleveloce matricitra velocimatrici 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. {{cita|Downey1995||Downey & Fellows (1995)|harv=s|Downey1995}} definirono una gerarchia di problemi parametrizzati, la gerarchia W, che congetturarono non avesse algoritmi trattabili a parametro fisso; essi provarono che l'inisiemeinsieme indipendente (o, equivalentemente, la cricca) è difficile per il primo livello di questa gerarchia, [[W(1)|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)|W[1]]]-difficoltà di molti altri problemi, e serve così come analogo del [[teorema di Cook-Levin]] per la complessità parametrizzata.

{{cita|Chen2006||Chen et al. (2006)|harv=s|Chen2006}} mostrarono che il problema della cricca non può essere risolto nel tempo <math>n^{o(k)}</math> 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 [[DegenrazioneDegenerazione (teoria dei grafi)|degenerazione]] del grafo delle entrate]].<ref name="ELS10"/>

=== Difficoltà di approssimazione ===

[[File:Cube-face-intersection-graph.svg|thumb|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 [[Sottografo indotto|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, {{cita|Garey1978||Garey & Johnson (1978)|harv=s|Garey1978}} 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 polinomiale|schema di approssimazione in tempo pienamente polinomiale]]. Tuttavia, poco di più si sapevaseppe fino ai primi anni 1990, quando parecchi autori cominciarono a fare connessioni tra l'approssimazione delle cricche massime e le [[Dimostrazione verificabile probabilisticamente|dimostrazioni verificabili probabilisticamente]], e usarono queste connessioni per dimostrare i risultati della [[difficoltà di approssimazione]] per il problema della cricca massima.<ref name="nyt"/></ref><ref>{{cita|Feige1991||Feige et al. (1991)|harv=s|Feige1991}}; {{cita|Arora1998a||Arora & Safra (1998)|harv=s|Arora1998a}}; {{cita|Arora1998b|Arora et al. (1998)|harv=s}}.</ref> Dopo molti miglioramenti in questi risultati s è ora noto che, a meno che [[Classi di complessità P e NP|P = NP]], non ci può essere nessun algoritmo in tempo polinomiale che approssima la cricca massima entro un fattore migliore di O(''n''^{1&nbsp;&minus;&nbsp;ε}), per qualsiasi ε&nbsp;>&nbsp;0.<ref>{{cita|Håstad1999||Håstad (1999)|harv=s|Håstad1999}} dimostrò l'inapprossimabilità per questo rapporto usando un'assunzione teorica di complessità più forte, la disuguaglianza di [[NP (complessità)|NP]] e [[ZPP (complessità)|ZPP]]; {{cita|Khot2001||Khot (2001)|harv=s|Khot2001}} descrisse più precisamente il rapporto di inapprossimazione, e {{cita|Zuckerman2006||Zuckerman (2006)|harv=s|Zuckerman2006}} [[Derandomizzazione|derandomizzò]] la costruzione indebolendo la sua assunzione a P&nbsp;≠&nbsp;NP.</ref>

L'idea generica di questi risultati di inapprossimabilità<ref>Questa riduzione è dovuta originariamente a {{cita|Feige1991||Feige et al. (1991)|harv=s|Feige1991}} 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.</ref> è 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 polinomailepolinomiale 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&nbsp;=&nbsp;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 ==

{| class="wikitable"

|-

!Nome<br />

!Licenza

!Linguaggio API

!Breve info

|-

|[[NetworkX]] ||[[BSD]]|| Python || soluzione approssimata, vedi la routine {{Collegamento interrotto|1=[http://networkx.lanl.gov/preview/reference/generated/networkx.algorithms.approximation.clique.max_clique.html max_clique] |data=luglio 2019 |bot=InternetArchiveBot }}

|-

|maxClique ||CRAPL|| Java || [http://www.dcs.gla.ac.uk/~pat/maxClique/distribution/ algoritmi esatti e istanze DIMACS]

|-

|[[OpenOpt]] ||[[BSD]]|| Python || soluzioni esatte e approssimate, possibilità di specificare i nodi che devono essere<br> />inclusi / esclusi; vedi la classe [http://openopt.org/MCP MCP] {{Webarchive|url=https://web.archive.org/web/20131003042139/http://openopt.org/MCP |data=3 ottobre 2013 }} per maggiori dettagli ed esempi

|}

== Note ==

{{<references|2}}/>

== Bibliografia ==

{{Div col|2}}

* {{cita testo |cognome1=Abello |nome1=J. |cognome2=Pardalos |nome2=P. M. |cognome3=Resende |nome3=M. G. C. |contributo=On maximum clique problems in very large graphs |titolo=External Memory Algorithms |curatore1-nome=J. |curatore1-cognome=Abello |curatore2-nome=J. |curatore2-cognome=Vitter |wkcuratore2 =Jeffrey Vitter |serie=DIMACS Serie on Discrete Mathematics and Theoretical Computer Science |volume=50 |pagine=119–130 |anno=1999 |editore=[[American Mathematical Society]] |url=http://www2.research.att.com/~mgcr/abstracts/vlclq.html |isbn=0-8218-1184-3 |cid= Abello1999 |accesso=26 marzo 2014 |urlarchivio=https://web.archive.org/web/20120229111804/http://www2.research.att.com/~mgcr/abstracts/vlclq.html |dataarchivio=29 febbraio 2012 |urlmorto=sì }}

* {{cita testo |nome1=N. |cognome1=Alon |wkautore1=Noga Alon |nome2=R. |cognome2=Boppana |titolo=The monotone circuit complexity of boolean functions |rivista=[[Combinatorica]] |volume=7 |numero=1 |anno=1987 |pagine=1–22 |doi=10.1007/BF02579196 |cid=Alon1987}}

* {{cita testo |nome1=N. |cognome1=Alon |wkautore1=Noga Alon |nome2=M. |cognome2=Krivelevich |nome3=B. |cognome3=Sudakov |titolo=Finding a large hidden clique in a random graph |rivista=Random Structures & Algorithms |volume=13 |numero=3–4 |anno=1998 |pagine=457–466 |doi=10.1002/(SICI)1098-2418(199810/12)13:3/4<457::AID-RSA14>3.0.CO;2-W |cid=Alon1998}}

* {{cita testo | cognome1 = Alon | nome1 = N. | wkautore1 = Noga Alon | cognome2 = Yuster | nome2 = R. | cognome3 = Zwick | nome3 = U. | contributo = Finding and counting given length cycles | pagine = 354–364 | titolo = Proceedings of the 2nd [[European Symposium on Algorithms]], Utrecht, The Netherlands | anno = 1994 |cid=Alon1994}}

* {{cita testo |nome1=K. |cognome1=Amano |nome2=A. |cognome2=Maruoka |contributo=A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log&nbsp;log&nbsp;''n'' negation gates |titolo=Proc. Symp. Mathematical Foundations of Computer Science |serie=Lecture Notes in Computer Science |anno=1998 |editore=[[Springer-Verlag]] |volume=1450 |pagine=399–408 |url=http://www.springerlink.com/content/m64ju7clmqhqmv9g/ |cid=Amano1998 |urlmorto=sì }}

* {{cita testo |titolo=Proof verification and the hardness of approximation problems |nome1=Sanjeev |cognome1=Arora |wkautore1=Sanjeev Arora |nome2=Carsten |cognome2=Lund |wkautore2=Carsten Lund |nome3=Rajeev |cognome3=Motwani |wkautore3=Rajeev Motwani |nome4=Madhu |cognome4=Sudan |author4-linkwkautore4=Madhu Sudan |nome5=Mario |cognome5=Szegedy |author5-linkwkautore5=Mario Szegedy |rivista=[[Rivista of the ACM]] |volume=45 |numero=3 |anno=1998 |pagine=501–555 |doi=10.11451109/278298SFCS.2783061992.267823 |id={{ECCC[[Electronic Colloquium on Computational Complexity|ECCC]]&nbsp;[http://eccc.uni-trier.de/report/1998|98|/008/ TR98-008]|cid=Arora1998a}}. presentatoPresentato originariamente al [[Symposium on Foundations of Computer Science]] del 1992, {{doi|10.1109/SFCS.1992.267823}} |cid=Arora1998a}}

* {{cita testo |nome1=S. |cognome1=Arora |wkautore1=Sanjeev Arora |nome2=S. |cognome2=Safra |wkautore2=Shmuel Safra |titolo=Probabilistic checking of proofs: A new characterization of NP |rivista=[[Rivista of the ACM]] |volume=45 |numero=1 |anno=1998 |pagine=70–122 |doi=10.11451109/273865SFCS.2739011992.267824 |id= presentato originariamente al [[Symposium on Foundations of Computer Science]] del 1992, {{doi|10.1109/SFCS.1992.267824}} |cid=Arora1998b}}

* {{cita testo |cognome1=Balas |nome1=E. |cognome2=Yu |nome2=C. S. |titolo=Finding a maximum clique in an arbitrary graph |rivista=[[SIAM Rivista on Computing]] |volume=15 |numero=4 |anno=1986 |pagine=1054–1068 |doi=10.1137/0215075 |cid=Balas1986}}

* {{cita testo |cognome1=Battiti |nome1=R. |cognome2=Protasi |nome2=M. |titolo=Reactive local search for the maximum clique problem |rivista=[[Algorithmica]] |volume=29 |numero=4 |anno=2001 |pagine=610–637 |doi=10.1007/s004530010074 |cid=Battiti2001}}

* {{Cita testo | cognome1=Bollobás | nome1=Béla | wkautore1=Béla Bollobás | titolo=Complete subgraphs are elusive | anno=1976 | rivista=Rivista of Combinatorial Theory, Serie B | issn=0095-8956 | volume=21 | numero=1 | pagine=1–7 | doi=10.1016/0095-8956(76)90021-6 |cid= Bollobás1976}}

* {{cita testo |nome1=I. M. |cognome1=Bomze |nome2=M. |cognome2=Budinich |nome3=P. M. |cognome3=Pardalos |nome4=M. |cognome4=Pelillo |contributo=The maximum clique problem |titolo=Handbook of Combinatorial Optimization |volume=4 |pagine=1–74 |editore=Kluwer Academic Editores |anno=1999 |id={{citeseerx|10.1.1.48.4074}} |cid=Bomze1999}}

* {{cita testo |nome1=R. |cognome1=Boppana |nome2=M. M. |cognome2=Halldórsson |titolo=Approximating maximum independent sets by excluding subgraphs |rivista=BIT |volume=32 |anno=1992 |pagine=180–196 |doi=10.1007/BF01994876 |numero=2 |cid=Boppana1992}}

* {{cita testo | cognome1=Bron | nome1=C. | cognome2=Kerbosch | nome2=J. | titolo=Algorithm 457: finding all cliques of an undirected graph | anno=1973 | rivista=[[Communications of the ACM]] | doi=10.1145/362342.362367 | volume=16 | numero=9 | pagine=575–577 |cid=Bron1973}}

* {{cita testo |cognome1=Carraghan |nome1=R. |cognome2=Pardalos |nome2=P. M. |titolo=An exact algorithm for the maximum clique problem |rivista=Operations Research Letters |volume=9 |anno=1990 |pagine=375–382 |url=http://www.inf.ufpr.br/renato/download/An_Exact_Algorithm_for_the_Maximum_Clique_Problem.pdf |numero=6 |doi=10.1016/0167-6377(90)90057-C |cid= Carraghan1990 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20110717210045/http://www.inf.ufpr.br/renato/download/An_Exact_Algorithm_for_the_Maximum_Clique_Problem.pdf |dataarchivio=17 luglio 2011 }}

* {{cita testo | cognome1=Cazals | nome1=F. | cognome2=Karande | nome2=C. | titolo=A note on the problem of reporting maximal cliques | url=ftp://ftp-sop.inria.fr/geometrica/fcazals/papers/ncliques.pdf | anno=2008 | rivista=[[Theoretical Computer Science (rivista)|Theoretical Computer Science]] | volume=407 | numero=1 | pagine=564–568 | doi=10.1016/j.tcs.2008.05.010 | cid=Cazals2008 | urlmorto=sì }}

* {{cita testo |nome1=Jianer |cognome1=Chen |nome2=Xiuzhen |cognome2=Huang |nome3=Iyad A. | cognome3=Kanj |nome4=Ge |cognome4=Xia | titolo=Strong computational lower bounds via parameterized complexity | rivista=J. Comput. Syst. Sci. | volume=72 | anno=2006 | pagine=1346–1367 | doi=10.1016/j.jcss.2006.04.007 |numero=8 |cid=Chen2006}}

* {{cita testo |nome1=N. |cognome1=Chiba |nome2=T. |cognome2=Nishizeki |titolo=Arboricity and subgraph listing algorithms |rivista=[[SIAM Rivista on Computing]] |volume=14 |numero=1 |pagine=210–223 |anno=1985 |doi=10.1137/0214017 |cid=Chiba1985}}

* {{cita testo |cognome1=Childs |nome1=A. M. |cognome2=Farhi |nome2=E. |cognome3=Goldstone |nome3=J. |wkautore3=Jeffrey Goldstone |cognome4=Gutmann |nome4=S. |titolo=Finding cliques by quantum adiabatic evolution |rivista=Quantum Information and Computation |volume=2 |numero=3 |pagine=181–191 |anno=2002 |arxiv=quant-ph/0012104 |cid=Childs2002}}

* {{cita testo |cognome1=Childs |nome1=A. M. |cognome2=Eisenberg |nome2=J. M. |titolo=Quantum algorithms for subset finding |rivista=Quantum Information and computation |volume=5 |numero=7 |pagine=593–604 |anno=2005 |arxiv=quant-ph/0311038 |cid=Childs2005}}

* {{cita testo | cognome1 = Clark | nome1 = Brent N. | cognome2 = Colbourn | nome2 = Charles J. | wkautore2= Charles Colbourn | wkautore3 = David S. Johnson | cognome3 = Johnson | nome3 = David S. | titolo = Unit disk graphs | rivista = [[Discrete Mathematics (rivista)|Discrete Mathematics]] | volume = 86 | numero = 1–3 | anno = 1990 | pagine = 165–177 | doi = 10.1016/0012-365X(90)90358-O |cid=Clark1990}}

* {{cita testo |nome=S. A. |cognome=Cook |wkautore=Stephen Cook |anno=1971 |titolo=Symposium on Theory of Computing|Proc. 3rd ACM Symposium on Theory of Computing |pagine=151–158 |url=http://4mhz.de/cook.html |doi=10.1145/800157.805047 |capitolo=The complexity of theorem-proving procedures |cid=Cook1971}}

* {{cita testo |nome1=R. G. |cognome1=Downey |wkautore2=Michael Fellows |nome2=M. R. |cognome2=Fellows |titolo=Fixed-parameter tractability and completeness. II. On completeness for W[1] |rivista=[[Theoretical Computer Science (rivista)|Theoretical Computer Science]] |volume=141 |numero=1–2 |anno=1995 |pagine=109–131 |doi=10.1016/0304-3975(94)00097-3 |cid=Downey1995}}

* {{cita testo |nome1=R. G. |cognome1=Downey |wkautore2=Michael Fellows |nome2=M. R. |cognome2=Fellows |titolo=Parameterized complexity | editore=[[Springer-Verlag]] | anno=1999 |isbn = 0-387-94883-X |cid=Downey1999}}

* {{cita testo |nome1=F. |cognome1=Eisenbrand |nome2=F. |cognome2=Grandoni |titolo=On the complexity of fixed parameter clique and dominating set |rivista=[[Theoretical Computer Science (rivista)|Theoretical Computer Science]] |volume=326 |numero=1–3 |pagine=57–67 |anno=2004 |doi=10.1016/j.tcs.2004.05.009 |cid=Eisenbrand2004}}

* {{cita testo |nome1=David |cognome1=Eppstein |wkautore1=David Eppstein |nome2=Maarten |cognome2=Löffler |nome3=Darren |cognome3=Strash |curatore1-cognome=Cheong |curatore1-nome=Otfried |curatore2-nome=Kyung-Yong |curatore2-cognome=Chwa |curatore3-nome=Kunsoo |curatore3-cognome=Park |titolo=21st International Symposium on Algorithms and Computation (ISAAC 2010), Jeju, Korea |serie=Lecture Notes in Computer Science |volume=6506 |pagine=403–414 |editore=Springer-Verlag |doi=10.1007/978-3-642-17517-6_36 |arxiv=1006.5440 |anno=2010 |chaptercapitolo=Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time |isbn=978-3-642-17516-9 |cid=Eppstein2010}}

* {{cita testo |nome1=David |cognome1=Eppstein |wkautore1=David Eppstein |nome2=Darren |cognome2=Strash |contributo=Listing all maximal cliques in large sparse real-world graphs |titolo=10th International Symposium on Experimental Algorithms |anno=2011 |arxiv=1103.0318 |cid= Eppstein2011}}

* {{cita testo |nome1=Paul |cognome1=Erdős |wkautore1=Paul Erdős |nome2=George |cognome2=Szekeres |wkautore2=George Szekeres |titolo=A combinatorial problem in geometry |rivista=Compositio Mathematica |volume=2 |anno=1935 |pagine=463–470 |url=http://www.renyi.hu/~p_erdos/1935-01.pdf |cid=Erdős1935}}

* {{cita testo |nome1=S. |cognome1=Even |wkautore1=Shimon Even |nome2=A. |cognome2=Pnueli |wkautore2=Amir Pnueli |nome3=A. |cognome3=Lempel |wkautore3=Abraham Lempel |titolo=Permutation graphs and transitive graphs |rivista=[[Rivista of the ACM]] |volume=19 |numero=3 |pagine=400–410 |anno=1972 |doi=10.1145/321707.321710 |cid=Even1972}}

* {{cita testo |nome=T. |cognome=Fahle |titolo=[[European Symposium on Algorithms|Proc. 10th European Symposium on Algorithms]] |serie=Lecture Notes in Computer Science |editore=Springer-Verlag |volume=2461 |anno=2002 |pagine=47–86 |doi=10.1007/3-540-45749-6_44 |chaptercapitolo=Simple and Fast: Improving a Branch-And-Bound Algorithm for Maximum Clique |isbn=978-3-540-44180-9 |cid=Fahle2002}}

* {{cita testo |nome=U. |cognome=Feige |wkautore=Uriel Feige |titolo=Approximating maximum clique by removing subgraphs |rivista=SIAM Rivista on Discrete Mathematics |volume=18 |numero=2 |pagine=219–225 |anno=2004 |doi=10.1137/S089548010240415X |cid=Feige2004}}

* {{cita testo |nome1=U. |cognome1=Feige |wkautore1=Uriel Feige |nome2=S. |cognome2=Goldwasser |wkautore2=Shafi Goldwasser |nome3=L. |cognome3=Lovász |wkautore3=László Lovász |nome4=S |cognome4=Safra |author4-linkwkautore4=Shmuel Safra |nome5=M. |cognome5=Szegedy |author5-linkwkautore5=Mario Szegedy |titolo=[[Symposium on Foundations of Computer Science|Proc. 32nd IEEE Symp. on Foundations of Computer Science]] |pagine=2–12 |anno=1991 |doi=10.1109/SFCS.1991.185341 |chaptercapitolo=Approximating clique is almost NP-complete |isbn=0-8186-2445-0 |cid=Feige1991}}

* {{cita testo |nome1=U. |cognome1=Feige |wkautore1=Uriel Feige |nome2=R. |cognome2=Krauthgamer |titolo=Finding and certifying a large hidden clique in a semirandom graph |rivista=Random Structures and Algorithms |volume=16 |numero=2 |pagine=195–208 |anno=2000 |doi=10.1002/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A |cid=Feige2000}}

* {{cita testo |nome1=M. R. |cognome1=Garey |wkautore1=Michael R. Garey |nome2=D. S. |cognome2=Johnson |wkautore2=David S. Johnson |titolo="Strong" NP-completeness results: motivation, examples and implications |rivista=[[Rivista of the ACM]] |volume=25 |pagine=499–508 |anno=1978 |doi=10.1145/322077.322090 |numero=3 |cid=GArey1978}}

* {{cita testo | cognome = Gavril | nome = F. | doi = 10.1002/net.3230030305 | numero = 3 | rivista = Networks | pagine = 261–273 | titolo = Algorithms for a maximum clique and a maximum independent set of a circle graph | volume = 3 | anno = 1973 |cid=Gavril1973}}

* {{cita testo |nome1=M. |cognome1=Goldmann |nome2=J. |cognome2=Håstad |wkautore2=Johan Håstad |titolo=A simple lower bound for monotone clique using a communication game |rivista=Information Processing Letters |volume=41 |numero=4 |anno=1992 |pagine=221–226 |doi=10.1016/0020-0190(92)90184-W |cid=Goldmann1992}}

* {{cita testo |nome=M. C. |cognome=Golumbic |wkautore=Martin Charles Golumbic |titolo=Algorithmic Graph Theory and Perfect Graphs |serie=Computer Science and Applied Mathematics |editore=[[Academic Press]] |anno=1980 |isbn=0-444-51530-5 |cid=Golumbic1980}}

* {{Cita testo | volume = 10 | numero = 3 | pagine = 119&ndash;127119–127 | cognome = Gröger | nome = Hans Dietmar | titolo = On the randomized complexity of monotone graph properties | rivista = Acta Cybernetica | accesso = 10-02- febbraio 2009 | anno = 1992 | url = http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf | cid = Gröger1992 | urlarchivio = https://web.archive.org/web/20150924034620/http://www.inf.u-szeged.hu/actacybernetica/edb/vol10n3/pdf/Groger_1992_ActaCybernetica.pdf | dataarchivio = 24 settembre 2015 | urlmorto = sì }}

* {{cita testo |nome1=A. |cognome1=Grosso |nome2=M. |cognome2=Locatelli |nome3=F. |cognome3=Della Croce |titolo=Combining swaps and node weights in an adaptive greedy approach for the maximum clique problem |rivista=Rivista of Heuristics |volume=10 |numero=2 |anno=2004 |pagine=135–152 |doi=10.1023/B:HEUR.0000026264.51747.7f |cid=Grosso2004}}

* {{cita testo |nome1=M. |cognome1=Grötschel |nome2=L. |cognome2=Lovász |wkautore2=László Lovász |nome3=A. |cognome3=Schrijver|wkautore3=Alexander Schrijver |titolo=Geometric Algorithms and Combinatorial Optimization |serie=Algorithms and Combinatorics |volume=2 |editore=[[Springer–Verlag]] |anno=1988 |contributo=9.4 Coloring Perfect Graphs |pagine=296–298 |isbn=0-387-13624-X |cid= Grötschel1998}}

* {{cita testo |nome=G. |cognome=Gutin |contributo=5.3 Independent sets and cliques |titolo=Handbook of graph theory |curatore1-nome=J. L. |curatore1-cognome=Gross |curatore2-nome=J. |curatore2-cognome=Yellen |editore=CRC Press |anno=2004 |isbn=978-1-58488-090-5 |pagine=389–402 |serie=Discrete Mathematics & Its Applications |cid=Gutin2004}}

* {{cita testo |titolo=Approximations of Weighted Independent Set and Hereditary Subset Problems |nome=M. M. |cognome=Halldórsson |rivista=[[Rivista of Graph Algorithms and Applications]] |volume=4 |numero=1 |pagine=1–16 |anno=2000 |url=http://jgaa.info/accepted/00/Halldorsson00.4.1.pdf |cid= Halldórsson2000}}

* {{cita testo |cognome1=Harary |nome1=F. |wkautore1=Frank Harary |cognome2=Ross |nome2=I. C. |titolo=A procedure for clique detection using the group matrix |rivista=Sociometry |volume=20 |anno=1957 |pagine=205–215 |doi=10.2307/2785673 |numero=3 |editore=American Sociological Association |mr=0110590 |jstor=2785673 |cid=Harary1957}}

* {{cita testo |nome=J. |cognome=Håstad |wkautore=Johan Håstad |titolo=Clique is hard to approximate within n^{1&nbsp;&minus;&nbsp;ε} |rivista=[[Acta Mathematica]] |volume=182 |numero=1 |pagine=105–142 |anno=1999 |doi=10.1007/BF02392825 |cid= Håstad1999}}

* {{cita testo |nome1=R. |cognome1=Impagliazzo |wkautore1=Russell Impagliazzo |nome2=R. |cognome2=Paturi |nome3=F. |cognome3=Zane |titolo=Which problems have strongly exponential complexity? |rivista=[[Rivista of Computer and System Sciences]] |volume=63 |numero=4 |anno=2001 |pagine=512–530 |doi=10.1006/jcss.2001.1774 |cid=Impagliazzo2001}}

* {{cita testo |nome1=A. |cognome1=Itai |nome2=M. |cognome2=Rodeh |titolo=Finding a minimum circuit in a graph |rivista=[[SIAM Rivista on Computing]] |volume=7 |numero=4 |pagine=413–423 |anno=1978 |doi=10.1137/0207033 |cid=Itai1978}}

* {{cita testo |nome=M. |cognome=Jerrum |titolo=Large cliques elude the Metropolis process |rivista=Random Structures and Algorithms |volume=3 |pagine=347–359 |anno=1992 |doi=10.1002/rsa.3240030402 |numero=4 |cid=Jerrum1992}}

* {{Cita testo | cognome1=Jian | nome1=T | titolo=An O(2^0.304''n'') Algorithm for Solving Maximum Independent Set Problem | editore=IEEE Computer Society | anno=1986 | rivista=IEEE Transactions on Computers | issn=0018-9340 | volume=35 | numero=9 | pagine=847–851 | doi=10.1109/TC.1986.1676847 |cid= Jian1986}}

* {{cita testo |curatore1-nome=D. S. |curatore1-cognome=Johnson |curatore1-linkwkcuratore1=David S. Johnson |curatore2-nome=M. A. |curatore2-cognome=Trick |titolo=Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, October 11–13, 1993 |serie=DIMACS Serie in Discrete Mathematics and Theoretical Computer Science |volume=26 |editore=[[American Mathematical Society]] |url=http://dimacs.rutgers.edu/Volumes/Vol26.html |anno=1996 |isbn=0-8218-6609-5 |cid=1996}}

* {{cita testo |nome1=D. S. |cognome1=Johnson |wkautore1=David S. Johnson |nome2=M. |cognome2=Yannakakis |wkautore2=Mihalis Yannakakis |titolo=On generating all maximal independent sets |rivista=Information Processing Letters |volume=27 |anno=1988 |pagine=119–123 |numero=3 |doi=10.1016/0020-0190(88)90065-8 |cid= Johnson1998}}

* {{cita testo | cognome=Karp |nome=Richard M. |wkautore=Richard M. Karp |url=httphttps://www.cs.berkeley.edu/~luca/cs172/karp.pdf |contributo= Reducibility among combinatorial problems |titolo=Complexity of Computer Computations |curatore1-nome=R. E. |curatore1-cognome=Miller |curatore2-nome=J. W. |curatore2-cognome=Thatcher |editore=[[Plenum Publishing Corporation|Plenum]] |città=New York |pagine=85–103 |anno=1972 |cid=Karp1972 |accesso=3 maggio 2019 |dataarchivio=4 marzo 2016 |urlarchivio=https://web.archive.org/web/20160304202627/http://www.cs.berkeley.edu/~luca/cs172/karp.pdf |urlmorto=sì }}

* {{cita testo | cognome=Karp |nome=Richard M. |wkautore=Richard M. Karp |contributo=Probabilistic analysis of some combinatorial search problems |titolo=Algorithms and Complexity: New Directions and Recent Results |curatore-nome=J. F. |curatore-cognome=Traub |editore=[[Academic Press]] |città=New York |anno=1976 |pagine=1–19 |cid=Karp1976}}

* {{cita testo |nome1=K. |cognome1=Katayama |nome2=A. |cognome2=Hamamoto |nome3=H. |cognome3=Narihisa |titolo=An effective local search for the maximum clique problem |rivista=Information Processing Letters |volume=95 |numero=5 |anno=2005 |pagine=503–511 |doi=10.1016/j.ipl.2005.05.010 |cid= Katayama2005}}

* {{cita testo |nome=S. |cognome=Khot |titolo=[[Symposium on Foundations of Computer Science|Proc. 42nd IEEE Symp. Foundations of Computer Science]] |pagine=600–609 |anno=2001 |doi=10.1109/SFCS.2001.959936 |chaptercapitolo=Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring |isbn=0-7695-1116-3 |cid=Khot2001}}

* {{cita testo |nome1=T. |cognome1=Kloks |nome2=D. |cognome2=Kratsch |nome3=H. |cognome3=Müller |titolo=Finding and counting small induced subgraphs efficiently |rivista=Information Processing Letters |volume=74 |numero=3–4 |pagine=115–121 |anno=2000 |doi=10.1016/S0020-0190(00)00047-8 |cid=Kloks2000}}

* {{cita testo |nome1=J. |cognome1=Konc |nome2=D. |cognome2=Janežič |titolo=An improved branch and bound algorithm for the maximum clique problem |rivista=MATCH Communications in Mathematical and in Computer Chemistry |volume=58 |numero=3 |pagine=569–590 |anno=2007 | url =http://www.sicmm.org/~konc/articles/match2007.pdf |cid=Konc2007 |accesso=26 marzo 2014 |urlarchivio=https://web.archive.org/web/20140327234740/http://www.sicmm.org/~konc/articles/match2007.pdf |dataarchivio=27 marzo 2014 |urlmorto=sì }} [https://web.archive.org/web/20140215114359/http://www.sicmm.org/~konc/maxclique/ Source code]

* {{cita testo |cognome1=Lipton |nome1=R. J. |wkautore1=Richard J. Lipton |cognome2=Tarjan |nome2=R. E. |wkautore2=Robert Tarjan |titolo=Applications of a planar separator theorem |rivista=[[SIAM Rivista on Computing]] |volume=9 |numero=3 |pagine=615–627 |anno=1980 |doi=10.1137/0209046 |cid=Lipton1980}}

* {{cita testo | cognome1 = Luce | nome1 = R. Duncan | wkautore1 = R. Duncan Luce | cognome2 = Perry | nome2 = Albert D. | titolo = A method of matrix analysis of group structure | rivista = Psychometrika | volume = 14 | numero = 2 | anno = 1949 | pagine = 95–116 | doi = 10.1007/BF02289146 | pmid = 18152948 |cid=Luce1949}}

* {{cita testo | cognome1 = Magniez | nome1 = Frédéric | cognome2 = Santha | nome2 = Miklos | cognome3 = Szegedy | nome3 = Mario | wkautore3 = Mario Szegedy | titolo = Quantum algorithms for the triangle problem | anno = 2007 | arxiv = quant-ph/0310134 | rivista = [[SIAM Rivista on Computing]] | volume = 37 | numero = 2 | pagine = 413–424 | doi = 10.1137/050643684 |cid= Magniez2007}}

* {{cita testo |nome=K. |cognome1=Makino |nome2=T. |cognome2=Uno |contributo=New algorithms for enumerating all maximal cliques |titolo=Algorithm Theory: SWAT 2004 |serie=Lecture Notes in Computer Science |editore=[[Springer-Verlag]] |volume=3111 |anno=2004 |pagine=260–272 |url=http://www.springerlink.com/content/p9qbl6y1v5t3xc1w/ |cid=Makino2004 |urlmorto=sì }}

* {{cita testo | cognome1 = Moon | nome1 = J. W. | wkautore2 = Leo Moser | cognome2 = Moser | nome2 = L. | titolo = On cliques in graphs | rivista = Israel Rivista of Mathematics | volume = 3 | anno = 1965 | pagine = 23–28 | mr = 0182577 | doi = 10.1007/BF02760024 |cid=Moon1965}}

* {{cita testo |wkautore1=Jaroslav Nešetřil |nome1=J. |cognome1=Nešetřil |wkautore2=Svatopluk Poljak |nome2=S. |cognome2=Poljak |titolo=On the complexity of the subgraph problem |rivista=Commentationes Mathematicae Universitatis Carolinae |volume=26 |numero=2 |pagine=415–419 |anno=1985 |cid=Nešetřil1985}}

* {{cita testo |nome=P. R. J. |cognome=Östergård |titolo=A fast algorithm for the maximum clique problem |rivista=Discrete Applied Mathematics |volume=120 |numero=1–3 |anno=2002 |pagine=197–207 |doi=10.1016/S0166-218X(01)00290-6 |cid=Östergård2002}}

* {{cita testo |cognome1=Ouyang |nome1=Q. |cognome2=Kaplan |nome2=P. D. |cognome3=Liu |nome3=S. |cognome4=Libchaber |nome4=A. |titolo=DNA solution of the maximal clique problem |rivista=[[Science (rivista)|Science]] |volume=278 |numero=5337 |pagine=446–449 |pmid=9334300 |doi=10.1126/science.278.5337.446 |anno=1997 |cid=Ouyang1997}}

* {{cita testo |cognome1=Pardalos |nome1=P. M. |cognome2=Rogers |nome2=G. P. |titolo=A branch and bound algorithm for the maximum clique problem |rivista=Computers & Operations Research |anno=1992 |volume=19 |numero=5 |pagine=363–375 |doi=10.1016/0305-0548(92)90067-F |cid=Pardalos1992}}

* {{cita testo |nome=A. A. |cognome=Razborov |wkautore=Alexander Razborov |titolo=Lower bounds for the monotone complexity of some Boolean functions |languagelingua =Russian ru |rivista=[[Proceedings of the USSR Academy of Sciences]] |volume=281 |anno=1985 |pagine=798–801 |postscript=Traduzione inglese in ''Sov. Math. Dokl.'' '''31''' (1985): 354–357 |cid=Razborov1985}}

* {{cita testo |nome=J.-C. |cognome=Régin |contributo=Using constraint programming to solve the maximum clique problem |titolo=Proc. 9th Int. Conf. Principles and Practice of Constraint Programming – CP 2003 |anno=2003 |url=http://www.springerlink.com/content/8p1980dfmrt3agyp/ |serie=Lecture Notes in Computer Science |editore=[[Springer-Verlag]] |volume=2833 |pagine=634–648 |cid=Régin2003 |urlmorto=sì }}

* {{cita testo |nome=J. M. |cognome=Robson |titolo=Algorithms for maximum independent sets |rivista=Rivista of Algorithms |volume=7 |anno=1986 |pagine=425–440 |numero=3 |doi=10.1016/0196-6774(86)90032-5 |cid=Robson1986}}

* {{Cita testo | cognome1=Robson | nome1=J. M. | titolo=Finding a maximum independent set in time O(2^''n''/4) |anno=2001 |url=http://www.labri.fr/perso/robson/mis/techrep.html |cid=Robson2001}}

* {{cita testo |cognome1=Rosgen |nome1=B |cognome2=Stewart |nome2=L |anno=2007 |titolo=Complexity results on graphs with few cliques |rivista=Discrete Mathematics and Theoretical Computer Science |volume=9 |numero=1 |pagine=127–136 |url=http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/707/1817 |cid=Rosgen2007 |urlmorto=sì |urlarchivio=https://web.archive.org/web/20150923215449/http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/707/1817 |dataarchivio=23 settembre 2015 }}

* {{cita testo |nome=M. |cognome=Sipser |wkautore=Michael Sipser |titolo=[[Introduction to the Theory of Computation]] |editore=[[The Thomson Corporation|International Thompson Publishing]] |anno=1996 |isbn=0-534-94728-X |cid=Sipser1996}}

* {{cita testo |nome1=R. E. |cognome1=Tarjan |wkautore1=Robert Tarjan |nome2=A. E. |cognome2=Trojanowski |titolo=Finding a maximum independent set |rivista=[[SIAM Rivista on Computing]] |volume=6 |anno=1977 |pagine=537–546 |url=ftp://db.stanford.edu/pub/cstr.old/reports/cs/tr/76/550/CS-TR-76-550.pdf |doi=10.1137/0206038 |numero=3 |cid=Tarjan1977 |urlmorto=sì }}

* {{cita testo |nome1=E. |cognome1=Tomita |nome2=T. |cognome2=Kameda |titolo=An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments |rivista=Rivista of Global Optimization |volume=37 |numero=1 |anno=2007 |pagine=95–111 |doi=10.1007/s10898-006-9039-7 |cid=Tomita2007}}

* {{cita testo |nome1=E. |cognome1=Tomita |nome2=T. |cognome2=Seki |titolo=Discrete Mathematics and Theoretical Computer Science |serie=Lecture Notes in Computer Science |editore=Springer-Verlag |volume=2731 |anno=2003 |pagine=278–289 |doi=10.1007/3-540-45066-1_22 |chaptercapitolo=An Efficient Branch-and-Bound Algorithm for Finding a Maximum Clique |isbn=978-3-540-40505-4 |cid=Tomita2003}}

* {{cita testo |nome1=E. |cognome1=Tomita |nome2=A. |cognome2=Tanaka |nome3=H. |cognome3=Takahashi |titolo=The worst-case time complexity for generating all maximal cliques and computational experiments |rivista=[[Theoretical Computer Science (rivista)|Theoretical Computer Science]] |volume=363 |numero=1 |pagine=28–42 |anno=2006 |doi=10.1016/j.tcs.2006.06.015 |cid=Tomita2006}}

* {{cita testo |nome1=S. |cognome1=Tsukiyama |nome2=M. |cognome2=Ide |nome3=I. |cognome3=Ariyoshi |nome4=I. |cognome4=Shirakawa |titolo=A new algorithm for generating all the maximal independent sets |rivista=[[SIAM Rivista on Computing]] |volume=6 |anno=1977 |pagine=505–517 |doi=10.1137/0206036 |numero=3 |cid=Tsukiyama1977}}

* {{cita testo |cognome=Valiant |nome=L. G. |titolo=[[Symposium on Theory of Computing|Proc. 15th ACM Symposium on Theory of Computing]] |anno=1983 |pagine=110–117 |doi=10.1145/800061.808739 |chaptercapitolo=Exponential lower bounds for restricted monotone circuits |isbn=0-89791-099-0 |cid=Valiant1983}}

* {{cita testo |nome1=V. |cognome1=Vassilevska |nome2=R. |cognome2=Williams |wkautore2=Ryan Williams (computer scientist) |titolo=[[Symposium on Theory of Computing|Proc. 41st ACM Symposium on Theory of Computing]] |anno=2009 |pagine=455–464 |doi=10.1145/1536414.1536477 |chaptercapitolo=Finding, minimizing, and counting weighted subgraphs |isbn=978-1-60558-506-2 |cid=Vassilevska2009}}

* {{cita testo |cognome=Wegener |nome=I. |titolo=On the complexity of branching programs and decision trees for clique functions |rivista=[[Rivista of the ACM]] |volume=35 |numero=2 |pagine=461–472 |anno=1988 |doi=10.1145/42282.46161 |cid=Wegener1998}}

* {{cita testo |nome=R. |cognome=Yuster |titolo=Finding and counting cliques and independent sets in ''r''-uniform hypergraphs |rivista=Information Processing Letters |volume=99 |numero=4 |pagine=130–134 |anno=2006 |doi=10.1016/j.ipl.2006.04.005 |cid=Yuster2006}}

* {{cita testo |nome=D. |cognome=Zuckerman |titolo=[[Symposium on Theory of Computing|Proc. 38th ACM Symp. Theory of Computing]] |pagine=681–690 |anno=2006 |doi=10.1145/1132516.1132612 |id={{ECCC[[Electronic Colloquium on Computational Complexity|ECCC]]&nbsp;[http://eccc.uni-trier.de/report/2005|05|/100}}/ TR05-100]|chaptercapitolo=Linear degree extractors and the inapproximability of max clique and chromatic number |isbn=1-59593-134-1 |cid=Zuckerman2006}}

{{Div col end}}

{{Portale|Matematica|Informatica|Matematica}}

[[Categoria:TeoriaProblemi computazionali nella teoria dei grafi|Cricca]]

[[Categoria:ComplessitàProblemi computazionaleNP-completi|Cricca]]

[[Categoria:Teoria della computazione]]

[[fr:Clique (théorie des graphes)#Problème de la clique]]