Problema della cricca

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

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

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.Per una rassegna di questi algoritmi e per le definizioni di base usate in questo articolo, vedi e .

Storia Sebbene i sottografi completi siano studiati da più tempo in matematica,I sottografi completi fanno una prima apparizione nella letteratura matematica nella riformulazione della teoria dei grafi della teoria di Ramsey da parte di . 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 , e il primo algoritmo per risolvere il problema della cricca è quello di , 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. Negli anni 1970, i ricercatori cominciarono a studiare questi algoritmi dal punto di vista dell'analisi del caso peggiore; vedi, per esempio, , un primo lavoro sulla complessità del caso peggiore nel problema della cricca massima. Sempre negli anni 1970, a cominciare dal lavoro di e , 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 e riportati all'epoca dai principali giornali, mostrarono che non è neanche possibile approssimare il problema in modo accurato ed efficiente.

Definizioni

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.

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 multiple, 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,. 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(nk k2): ci sono O(nk) sottografi da controllare, ciascuno dei quali ha O(k2) 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.Ad es., vedi .

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ù Θ(m3/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 Ω(m3/2) nel caso peggiore, e si conoscono algoritmi che si abbinano a questo limite temporale. forniscono un algoritmo con tempo di esecuzione O(m3/2) che trova un triangolo se ne esiste uno, ma non elenca tutti i triangoli; elencano tutti i triangoli nel tempo O(m3/2). Per esempio, 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(m1/2), questo algoritmo funziona nel tempo O(m3/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à. 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 , 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(n2,376), che può essere più veloce di O(m3/2) per grafi sufficientemente densi. hanno migliorato l'algoritmo O(m3/2) per trovare i triangoli a O(m1,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.; ; ; ; .

Elencare tutte le cricche massimali