Spectral approximation algorithms for graph cut problems

(1)

Spectral Approximation Algorithms for Graph Cut

Problems

Giuseppe Ottaviano

Il problema del massimo taglio in un grafo (MC) consiste nel trovare una partizione dei nodi in due parti tali che gli archi con un estremo nella partizione e un estremo nell’altra siano massimizzati. È uno dei problemi combinatoriali su grafi più naturali e interessanti. Sfortunatamente come molti dei problemi interessanti è NP-completo: è uno dei  problemi di cui Karp ha dimostrato la NP-completezza nell’articolo del  che ha gettato le basi della teoria delle riduzioni.

Esclusa quindi l’esistenza di algoritmi efficienti ed esatti (assumendo che P x NP), la ricerca sui problemi di ottimizzazione combinatoria si `e spostata su due fronti duali:

• Lo sviluppo di algoritmi approssimati, cio`e che trovano una soluzione subotti-male al problema, ma dimostrabilmente vicina alla soluzione ottima.

• La teoria dell’inapprossimabilit`a, che studia la massima precisione che possono raggiungere gli algoritmi polinomiali.

Qualora si dimostri che un problema non è approssimabile oltre un certo limite teorico (solitamente una funzione dell’ottimo), e che tale limite è raggiunto da un algoritmo di approssimazione, la complessità approssimata del problema è essenzial-mente risolta, in quanto sia l’algoritmo che il risultato di inapprossimabilità sono ottimali.

In questa tesi descriviamo un algoritmo presentato in un recente lavoro di Tre-visan che sfrutta tecniche spettrali per l’approssimazione di MC. L’obiettivo di questa tesi `e fornire una sua analisi sperimentale che dimostra che l’algoritmo `e applicabile a problemi di grandi dimensioni.

Per poter sviluppare la tesi, richiameremo il concetto di Laplaciano di un grafo e alcuni risultati elementari di teoria spettrale dei grafi. Definiremo i problemi di SC e edge expansion, le disuguaglianze alla Cheeger e l’algoritmo di parti-zionamento spettrale, che sono le prime applicazioni storiche della teoria spettrale e che hanno ispirato l’algoritmo spettrale per MC.

Nel seguito concentreremo l’attenzione su MC. Descriveremo l’algoritmo di Goemans e Williamson, che in un articolo del  hanno presentato la prima

(2)

approssimazione non banale, con precisione αGW _min_BθBπ_π θ

cos θ . . . .,

cio`e che restituisce una soluzione di valore almeno αGW _{volte l’ottimo. L’algoritmo}

si basa su un rilassamento geometrico di un problema di programmazione quadra-tica intera equivalente a MC. Tale problema `e formulabile come programma semidefinito, quindi risolubile in tempo polinomiale. La soluzione del rilassamento viene quindi arrotondata cos`ı da ottenere una soluzione ammissibile del programma quadratico intero.

Non è stato scoperto alcun algoritmo che garantisca un rapporto di approssima-zione al caso pessimo migliore di quello di Goemans-Williamson. Vedremo come la Unique Games Conjecture, una recente congettura di Khot et al., implicherebbe l’ottimalità dell’algoritmo semidefinito. Tale congettura è adoperata per la costruzione di un verificatore PCP (Probabilistically Checkable Proof ) riducibile a MC. L’a-nalisi del verificatore si basa su una congettura recentemente dimostrata: il teorema Majority is Stablest, sulle proprietà estremali delle funzioni monotone , nÐ R. Altro ingrediente fondamentale è l’analisi di Fourier delle funzioni finite, un campo recentemente in fermento per le sue applicazioni in combinatoria e informatica teorica.

Infine presenteremo l’algoritmo spettrale per MC. A differenza degli approc-ci tipo Goemans-Williamson, basati su programmazione semidefinita, esso fa uso dell’autovettore principale del Laplaciano per trovare un’immersione del grafo nella retta. Tramite un algoritmo lineare di arrotondamento `e quindi possibile estrarre dall’immersione sottografi con buoni tagli, e ripetere ricorsivamente il procedimento. Il rapporto di approssimazione raggiunto `e almeno . . . ..

Rispetto all’algoritmo semidefinito, l’algortimo spettrale ha un’analisi elementare ed è facilmente implementabile, visto che l’unico passo complesso consiste nel calcolo di un autovettore di una matrice sparsa quanto il grafo. Sfruttando librerie esistenti per il calcolo numerico di autovettori di matrici sparse, è possibile applicare l’algo-ritmo a grafi di dimensioni consistenti. Presenteremo quindi un’implementazione e un’analisi sperimentale, che mostra che l’algortimo è molto efficiente in pratica, e che pone nuovi problemi aperti sulla sua analisi teorica.

Relatori:

Prof. Roberto Grossi, Universit`a di Pisa

Prof. Luca Trevisan, University of California - Berkeley