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