Il problema della massima clique : teoria & pratica

Abstract

Il problema di trovare le clique di un grafo appartiene a quel gruppo di problemi combinatoriali considerati un "paradigma" nell'ambito della Teoria della Complessità Computazionale. L'idea principale di questo lavoro è quella di sfruttare la meccanica statistica, la teoria sui vetri di spin e le proprietà delle catene di Markov per creare, comprendere e sviluppare due nuovi algoritmi random per la ricerca della clique: un Metropolis (M) con dinamica alla Glauber ed un algoritmo ispirato al metodo della cavità (C). La possibilità di associare questi algoritmi a modelli disordinati di gas su reticolo, ci permette di utilizzare strumenti tipici della fisica teorica per valutarne caratteristiche e peculiarità. La novità principale rispetto agli altri algoritmi standard che C e M possono esibire è la possibilità di "camminare" su configurazioni che non sono cliques. In questa maniera sembrano avere a disposizione più vie d'uscita quando rimangono intrappolati in uno "stato metastabile" che non sia l'ottimo. Al confronto con altri algoritmi random più famosi, le prestazioni di questi nuovi algoritmi sono decisamente migliori. In particolare, alla luce di costosissime simulazioni numeriche, la dinamica originale di C, che ha oltretutto il vantaggio di essere teoricamente ben comprensibile ed in grado di presentare adeguatamente le problematiche in gioco, sembra decisamente promettente.