Università degli Studi di Roma Tor Vergata Facoltà di Ingegneria Corso di Laurea in Ingegneria dei...

Università degli Studi di Roma Tor Università degli Studi di Roma Tor VergataVergata Facoltà di IngegneriaFacoltà di IngegneriaCorso di Laurea in Ingegneria dei Modelli e dei SistemiCorso di Laurea in Ingegneria dei Modelli e dei Sistemi A.A. 2008/2009 A.A. 2008/2009

Analisi della complessità di algoritmi Analisi della complessità di algoritmi risolutivi per il problema del massimo risolutivi per il problema del massimo

insieme stabile in grafi claw-free.insieme stabile in grafi claw-free.Laureando:Marco Senatore

Relatore: Prof. Gianpaolo Oriolo

Co-Relatore: Dr. Yuri Faenza

Tesi di Laurea Specialistica

Obiettivo della TesiObiettivo della Tesi

L’ obiettivo di questa Tesi consiste nell’analizzare la complessità:

dell’algortimo di Minty per la soluzione del problema del massimo insieme stabile su grafi claw-free

dell’estensione di tale algoritmo al caso pesato, revisionata sia da Schrijver che da Nakamura e Tamura.

Una questione apertaUna questione aperta

E’ noto che gli algoritmi menzionati hanno complessità polinomiale, ma non se ne conosce l’ordine.

In letteratura le affermazioni al riguardo risultano contrastanti:

Sia Minty che Nakamura e Tamura non forniscono dettagli.

Lozin e Milanic danno una stima approssimativa pari ad O( n7 ).

Oriolo, Pietropaoli e Stauffer riportano O( n6 )

Perché tale obiettivo ?

SommarioSommario

Il problema del massimo insieme stabile.Il problema del massimo insieme stabile. Risultati e contributi:Risultati e contributi:

Complessità caso non pesato.Complessità caso non pesato. Complessità caso pesato (con Complessità caso pesato (con

modifiche minori).modifiche minori). Conclusioni e sviluppi futuri.Conclusioni e sviluppi futuri.

Il problema del massimo insieme Il problema del massimo insieme stabilestabile

Def: Sia G = G(V,E) un grafo non orientato. Un sottoinsieme S di V è detto insieme stabile se per ogni coppia di vertici in S non esiste un arco di G che li collega. S

PROBLEMA: Dato un grafo G il problema del massimo insieme stabile consiste nel trovare, tra tutti gli insiemi stabili di G, quello di cardinalità massima.

PROBLEMA: Dato un grafo G ed una funzione di costo w: V → R+ il problema del massimo insieme stabile pesato consiste nel trovare l’insieme stabile S di G che massimizza il valore Σw(si), per si S.

Analisi della complessitàAnalisi della complessità

È possibile descrivere la complessità di un algoritmo mediante una funzione che esprima l’ordine di grandezza del numero di operazioni elementari compiute, in funzione della dimensione dell’input (n).

Un algoritmo si dice polinomiale se termina in un numero di passi limitato da un polinomio nella dimensione dell’input.

Il problema del massimo stabile è NP-Completo, ovvero si congettura fortemente non possa essere risolto in tempo polinomiale.

I grafi claw-freeI grafi claw-free

Un grafo è Un grafo è claw-freeclaw-free se non ammette come sottografo indotto il claw. se non ammette come sottografo indotto il claw.

“Su un grafo claw-free il problema del massimo insieme stabile può essere risolto in tempo polinomiale.”

Minty, 1980

I grafi claw-free furono inizialmente introdotti come generalizzazione dei line graph, evidenziando un profondo legame tra il problema del massimo stabile e quello del massimo matching su un grafo.

Il MatchingIl Matching

Il problema del massimo insieme stabile su un grafo claw-free può essere considerato Il problema del massimo insieme stabile su un grafo claw-free può essere considerato una generalizzazione del problema del una generalizzazione del problema del matching, matching, che, che, dato un grafo non orientato G, dato un grafo non orientato G, consiste nel trovare un consiste nel trovare un matching massimomatching massimo su di esso. su di esso.

Def: Sia G = G(V,E) un grafo non orientato. Un sottoinsieme M di E è detto matching se non ci sono in M due archi incidenti sullo stesso nodo.

Un nodo su cui non insiste alcun arco di M si dice esposto.

M

Dato un grafo G(V,E) ed una funzione di costo w: E → R+ il problema del massimo matching pesato consiste nel trovare il matching M di G che massimizza il valore Σw(e), con e M.

Line graphLine graphDato un grafo G, il suo line graph L(G) si costruisce nel seguente modo:Dato un grafo G, il suo line graph L(G) si costruisce nel seguente modo: ogni vertice di L(G) corrisponde ad un arco di G; due vertici di L(G) sono adiacenti se e solo se i loro archi corrispondenti sono adiacenti in G.

a b

c

f

e

d

g h

G

g

a

b

c

d

e

f

h

L(G)

Line graphLine graph

Un matching su un grafo G equivale ad uno stabile nel corrispondente line graph L(G).

b

a b

c

f

e

d

g h

G a c

d

e

f

h

L(G)

g

Problema del matchingProblema del matchingDef: Un cammino P su un grafo G(V,E) è detto alternante rispetto a un matching M su G, o M-alternante, se gli archi di P appartengono alternativamente a M e al suo complementare, E\M.

Def: Un cammino M-alternante P è detto M-aumentante se entrambi i suoi vertici estremi sono esposti rispetto al matching M.

P

M

TEOREMA (Berge, 1957; Norman e Rabin, 1959)Un matching M in un grafo G(V,E) è massimo se e solo se non ci sono cammini M-aumentanti in G.

L’algoritmo di L’algoritmo di EdmondsEdmonds

Edmonds per primo fornì un algoritmo che risolvesse il problema del matching Edmonds per primo fornì un algoritmo che risolvesse il problema del matching in O(nin O(n44):):

1. M =

2. While ( un cammino M-aumentante P) do

3. Poni M = M ∆ P

4. End while

5. M è il massimo matching

O(n2)

L’algoritmo di MintyL’algoritmo di Minty

Def: Dato un grafo G ed uno stabile S su di esso un cammino P = (v0, v1, ....., vk) è detto S-aumentante, se:

precisamente uno tra vi-1 e vi appartiene ad S, per ogni i=1, ......, k;

v0 e vk non appartengono allo stabile S;

(S\{v1, v3, ....., vk-1}) {v0, v2, ....., vk} è stabile.

L’idea dell’algoritmo di Minty è di generalizzare l’algoritmo di Edmonds per la ricera del massimo matching.

v0

v6

k=6

v0

v6


Dato uno stabile S su G costruiremo un nuovo grafo H con un matching M su di esso e noteremo che:

un cammino S-aumentante a-b su G

TEOREMA Dato un grafo claw-free G ed uno stabile S su di esso, esiste uno stabile di cardinalità |S|+1 se e solo se esiste un cammino S-aumentante.

1. S =

2. For (a, b V \ S) do

3. if esiste un cammino S-aumentante tra a e b then

4. aumenta S e vai a 2

5. end if

6. End for

7. S è il massimo insieme stabile cercato

un cammino M-aumentante su H

Il Pre-processamentoIl Pre-processamento

Oss: Non tutte le coppie a e b ammettono un cammino S-aumentante P.

I a ha un unico vicino sa S, mentre b ha un unico vicino sb S.

a sa bsb

II ogni v V \ S, v a, b, ha esattamente due vicini nello stabile.

v

III ogni s S, s sa, sb, ha almeno due vertici in S a distanza due

s

Un’ idea dell’algoritmoUn’ idea dell’algoritmo

Dividiamo l’insieme S in due sottoinsiemi:

S’ l’insieme dei vertici splittablesplittable

S’’ = S \ S’S’’ = S \ S’

Consideriamo il sottografo di G indotto da (V \ S’, δ(S’’) ). Chiamiamo ogni sua componente bone.

a

t

sa

sb b

s

z


zt

s

sa

a

sb b

sa

zz

sb

ss

tt

Introduciamo il grafo di Edmonds H


sa

zz

sb

ss

tt

P


Introduciamo il grafo di Edmonds H

a

t

sa

sb b

s

z


Abbiamo trovato un cammino a-b S-aumentante!

Complessità caso non Complessità caso non pesatopesato1. Inizializzazione1 // O(n2)

2. While ( S non è di cardinalità massima ) do // O(n)

3. Inizializzazione2 // O(n3)

4. For a, b V \ S do // O(n2)

5. Pre-processamento //O(n3)

6. Creazione di S’ e di S’’ // O(n2)

7. Creazione dei bone e di H // O(n3)

8. Ricerca di un cammino M-aumentante su H // O(n3)

9. Aggiornamento di S // O(n2)

10. End for

11. End while

O(n6) ?

Complessità caso non Complessità caso non pesatopesato

Abbiamo:

Implementato in modo più efficiente i passi Pre-processamento e Creazione dei bone e di H, ottenendo O(n2).

Considerato la particolare istanza del problema del matching su H:

Il matching su H è “quasi” perfetto

E’ sufficiente una sola iterazione che ha costo O(n2)

Complessità caso non Complessità caso non pesatopesato




4. For a, b V \ S do // O(n2)




8. Ricerca di un cammino M-aumentante su H // O(n2)


10. End for

11. End while

O(n5)

Il caso pesatoIl caso pesato

La costruzione mostrata fino ad ora si può estendere al caso pesato.

Abbiamo:

un grafo G = (V, E);

una funzione w : V → R+ .

Problema: trovare un insieme stabile S che massimizza Σw(si), dove si S

Def : un insieme stabile S è detto estremo se ha il peso massimo tra tutti gli insiemi stabili di cardinalità |S|.

Basterà trovare un algoritmo che ci permetta di passare da un qualsiasi stabile estremo S ad uno stabile estremo di cardinalità |S|+1.

LEMMA :

Sia G = (V, E) un grafo claw-free, data w : V → R+, e sia S un insieme stabile estremo su G. Allora:

(i) ogni circuito S-alternante senza corde C soddisfa w(VC \ S) w(VC S);

(ii) se P è un cammino S-aumentante che massimizza w(VP \ S) - w(VP S), allora S ∆ VP è un insieme stabile estremo di cardinalità |S| + 1.

Quindi per trovare un insieme stabile estremo di cardinalità |S| +1 è sufficiente trovare un cammino P S-aumentante che massimizza w(VP \ S) - w(VP S).


(s, X) (s, Y)

(t, X) (t, Y)

L’algoritmo per il massimo matching pesato restituisce:

• cammini M-aumentanti che aumentano il peso del matching;

• cicli M-alternanti che aumentano il peso del matching.

Potrebbe non corrispondere ad un circuito S-alternante senza corde

Revisione di Schrijver


La revisione di La revisione di SchrijverSchrijver

(s,X)

(t,Y)

(s,Y)

(t,X)

1

1

33 3

3

2

1

2

1 1

2

1

2

st

z

u1

v3

v2

v1

u2

Schrijver ovviò al problema, introducendo due ulteriori condizioni:

1. Una da incorporare nella fase di pre-processamento

2. Una da verificare in seguito alla creazione di S’ ed S’’

(s,X) (s,Y)

(t,X) (t,Y)

(z,X)

(z,Y)

1

1

1

2 2

222

1

2

1 1

2

2

st

z

u1

v2

v1

u2

La revisione di La revisione di SchrijverSchrijver

Al termine della revisione H non presenta cicli M-aumentanti

Complessità caso pesatoComplessità caso pesato




4. For a, b V \ S do // O(n2)




8. Ricerca di un massimo cammino M-aumentante su H // O(n(m+nlogn))


10. End for

11. End whileO(n5 + n4(m + nlogn)) , m=O(n2)

Il collo di bottigliaIl collo di bottiglia

Il collo di bottiglia corrisponde alla fase Il collo di bottiglia corrisponde alla fase Ricerca di un massimo cammino M-aumentante su H

Necessità di risolvere un intero problema di massimo matching pesato

L’algortimo di Gabow è il più efficiente: O(n(m+nlogn))

Possiamo migliorare?

Probabilmente si Grazie alla revisione effettuata dobbiamo risolvere un’istanza

particolare del problema del massimo matching pesato

Conclusioni e sviluppi Conclusioni e sviluppi futurifuturi Complessità per il caso non pesato O(n5)

Complessità per il caso pesato O(n5 + n4(m + nlogn)) → leggero miglioramento rispetto ad O(n6)

Migliorare l’efficienza nel caso pesato ottenendo O(n5)

Individuare ulteriori margini di miglioramento a partire dal numero di iterazioni

Applicazioni del problema del massimo insieme stabile

Un’universita’ organizza una giornata sportiva per le matricole. Per dare massima rilevanza all’evento vuole massimizzare il numero di partite il Sabato alle 14, quando una troupe televisiva verra’ a filmare l’evento.

Applicazioni del problema del massimo insieme stabile

Claudio pallavolo, salto in lungo

Gino pallamano, pallavolo, baseball

Giulia basket, salto in lungo, baseball

Luca pallavolo, corsa

Maria rugby, corsa

Mario calcio, rugby

Silvia basket, pallamano, salto in lungo

Paolo hockey su prato, pallamano, calcio

pallavolo

baseball

salto in lungo

corsa

hockey su prato

rugby calcio

basketpallamano

Analisi della Analisi della complessitàcomplessitàCOMPLESSITA’ DI UN ALGORITMO:

Misura del numero di passi che si devono eseguire per risolvere il problema.

COMPLESSITA’ DI UN PROBLEMA:

Complessità del migliore algoritmo che risolve il problema in questione

EFFICIENZA ASINTOTICA:

Come aumenta il tempo di esecuzione di un algoritmo al crescere della dimensione dell’input al limite

LIMITE SUPERIORE ASINTOTICO:

Se f(n) = O(g(n)) è il tempo di calcolo richiesto da un algoritmo Alg, diciamo che O(g(n)) è un limite superiore asintotico per la complessità di Alg.

P=NP ?P=NP ?

P:= problemi di decisione che possono essere risolti in tempo polinomiale

NP:= problemi di decisione le cui soluzioni positive sono verificabili in tempo polinomiale

P=NP?

Problemi NP-completi

Cammini S-aumentanti Cammini S-aumentanti

TEOREMA Dato un grafo claw-free G ed uno stabile S su di esso, condizione necessaria e sufficiente per l’esistenza di uno stabile con cardinalità maggiore è l’esistenza di un cammino S-aumentante.

Dim: poiché la sufficienza segue ovviamente dalla definizione di cammino S-aumentante concentriamoci sulla necessarietà.

Sia S’ uno stabile su G tale che |S’| > |S|. Si consideri il sottografo indotto da S’∆S: i nodi delle sue componenti hanno grado al più due perché altrimenti avrei il claw.

S S’

Cammini S-aumentantiCammini S-aumentanti

Le componenti di S’∆S possono essere solo cammini o cicli pari in cui si alternano elementi di S ed S’:

Poichè |S’| > |S| esiste almeno una componente K che ha più nodi appartenenti ad S’ che ad S e, poiché soddisfa la definizione, K è un cammino S-aumentante.

L’algoritmo di Minty: L’algoritmo di Minty: preprocessamentopreprocessamento

Fissiamo a, b V \ S e assumiamo:

a b, con deg(a) = deg(b) = 1;

a e b hanno un vicino in S, sa e sb , con sa sb ;

ogni v V \ S, con v a,b , ha esattamente due vicini in S;

ogni s S, con s sa , sb , ha almeno due vertici in S ha distanza due;

G è connesso.

a sa bsb

a sa bsb

Consideriamo il cammino S-alternante:

P = (v0 , s1 , v1 , ........, sk , vk) , con v0 = a , vk = b. Allora:

LEMMA : P è S-aumentante sse vi-1 e vi sono non adiacenti i = 1, ......, k-1.

L’algoritmo di MintyL’algoritmo di MintyDef : Dati u,v V\S:

u v (ovvero u è simile a v) N(u) S = N(v) Su

v

Def : s S è splittable se N(s) può essere partizionato in due classi X,Y tali che:

uv E u, v X oppure u,v Y, u, v N(s), con u v

Y

s

w v

zu

• u v ;

• z w ;

• z u ;

• w v.

X


Definiamo:

• S’ = {s S tale che s è splittable};

• S’’ = S\S’.

OSS : sa, sb appartengono ad S’, quindi sono splittable.

Vale inoltre il seguente:

LEMMA : Ogni vertice s S’ che ha almeno tre vertici in S a distanza due, appartiene ad S’.

Ogni s S’’ ha al più due vertici in S a distanza due.


Ora consideriamo il sottografo di G indotto da (V \ S’, δ(S’’) ). E’ un grafo bipartito; chiameremo ogni sua componente BONE.

Ogni bone è costituito da una serie di vertici s1, ..........., sk in S’’ e da insiemi di vertici non vuoti e disgiunti V0 , V1, ..........., Vk tali che si è adiacente ad ogni vertice di Vi-1 Vi per ogni i = 1,...., k. Inoltre un bone ha due vicini in S’.

L’algoritmo di MintyL’algoritmo di MintySe togliamo da un cammino S-aumentante i vertici che appartengono ad S’, rimaniamo con un certo numero di sottocammini, ognuno dei quali è un cammino S’’-aumentante contenuto in qualche bone.

Quindi i cammini S-aumentanti possono essere decomposti in cammini S’’-aumentanti che si congiungono tra loro tramite vertici splittable .

Qui le classi X ed Y dei vertici splittable entrano in gioco, poiché le estremità dei due sottocammini che si congiungono in s S’ devono appartenere a classi diverse di s.

X X YY

s t

IL CAMMINO VERDE E’ S-AUMENTANTE


Introduciamo il Grafo di Edmonds H = (W, F).

W = {(s, X) | s S’, X classe di s} \ { (sa, {a}), (sb, {b}) }

F = (i) { (s, X), (s, Y) } per s S’ \ {sa , sb} e X,Y le classi di s;

(ii) { (s, X), (t, Y) } per i vertici di H (s, X), (t, Y) tali che esiste un cammino P

S’’-aumentante che va da X ad Y.

(t, X)(t, Y)

(s, Y)(s, X)

(z, X)

(z, Y)

(sa , N(sa) \ {a})

(sb , N(sb) \ {b})


(t, X)(t, Y)

(s, Y)(s, X)

(z, X)

(z, Y)

(sa , N(sa) \ {a})

(sb , N(sb) \ {b})

Sia M il matching sugli archi di H del tipo (ii). Quindi M copre tutti i vertici di H eccetto (sa , N(sa) \ {a}) e (sb , N(sb) \ {b}).

M


LEMMA : G ha un cammino S-aumentante H ha un cammino M-aumentante

(t, X)(t, Y)

(s, Y)

(s, X)

(z, X)

(z, Y)

(sa , N(sa) \ {a})

(sb , N(sb) \ {b})

M

t s zsa

a

sb

b

IL MASSIMO INSIEME STABILE IN UN GRAFO CLAW-FREE PUO’ ESSERE TROVATO IN TEMPO POLINOMIALE.

L’implementazione: il pre-L’implementazione: il pre-procproc

II proprietà:

• per ogni v V \ S, v a, b, definiamo un intero Kv pari al numero di elementi appartenenti allo stabile che sono nell’intorno di v.

• per ogni v V \ S, v a, b per i quali Kv = 2 definiamo un vettore bidimensionale Fv in cui memorizziamo i vicini di v.

v

z

Kv = 1

v

zw

Kv = 2w z

Fv =

Affinchè un nodo v V \ S, v a, b verifichi la II proprietà deve valere Kv = 2.

L’implementazione: il pre-L’implementazione: il pre-procproc

III proprietà:

• per ogni t S, s S, con t N(s) un vettore n-dimensionale At tale che At [s] è pari a z se z S è l’unico nodo dello stabile che appartiene a N2(s) N(t), a -1 altrimenti.

• per ogni s,z S, un vettore n-dimensionale Bz tale che Bz [s] indica il numero di nodi t S tali che At [s] = z, ovvero il numero di vertici non appartenenti allo stabile che appartengono a N(s) N(z).

• per ogni s S, un intero Rs pari al numero di nodi dello stabile nel secondo intorno di s.

s zt

w

u

At [s] = z , Bz [s] =2

Au [s] = w , Bw [s] =1

Rs = 2

Affinchè un nodo s S, s sa, sb verifichi la III proprietà deve valere Rs ≥ 2.

LEMMA :

Sia G = (V, E) un grafo claw-free, data w : V → R+, e sia S un insieme stabile estremo su G. Allora:

(i) ogni circuito S-alternante senza corde C soddisfa w(VC \ S) w(VC S);

(ii) se P è un cammino S-aumentante che massimizza w(VP \ S) - w(VP S),

allora S ∆ VP è un insieme stabile estremo di cardinalità |S| + 1.

Dim. :

(i) Notiamo che S ∆ VC è uno stabile di cardinalità |S| e quindi poiché S e estremo vale w(S) ≥ w(S ∆ VC) = w(S) – w(VC S) + w(VC \ S)

w(VC \ S) w(VC S)

L’algoritmo di Minty nel caso L’algoritmo di Minty nel caso pesatopesato

(ii) Sia Z uno stabile estremo di cardinalità |S| + 1. Il sottografo indotto da S ∆ Z ha almeno una componente K tale che |K Z| = |K S| + 1. Poiché G è claw-free, K ha grado al più due, quindi K è un cammino S-aumentante.

Definisco L : = (S ∆ Z) \ K. Allora S ∆ L e Z ∆ L sono insiemi stabili di cardinalità |S| e |S| + 1 rispettivamente.

Poiché S è estremo vale w(S ∆ L) w(S). Ma w(S ∆ L) = w(S) – w(L S) + w(L \ S) w(L \ S) w(S L) w(L Z) w(S L).

Analogamente dall’estremalità di Z segue w(L Z) ≥ w(S L).

w(L Z) = w(S L) Z’: = Z ∆ L è ancora estremo con cardinalità |S|+1. Si nota che S ∆ Z’ ≡ K L = .

Ricordiamo che K è un cammino S-aumentante:

w(VP \ S) - w(VP S) ≥ w(K\ S) - w(K S)

w (VP ∆ S) ≥ w(K ∆ S) = w(Z’) VP ∆ S è estremo.



Quindi per trovare un insieme stabile di cardinalità |S| +1 è sufficiente trovare un cammino P S-aumentante che massimizza w(VP \ S) - w(VP S).

Rispetto al caso pesato dobbiamo solo aggiungere una funzione peso f per gli archi di H nel seguente modo:

f ({ (s, X), (s, Y) } ) : = w(s);

f ({ (s, X), (t, Y) } ) : = il massimo di w(VP \ S’’) - w(VP S’’) su tutti i cammini P da X ad Y S’’-aumentanti.

PROBLEMA: Non sempre un matching di massimo peso su H conduce ad uno stabile di massimo peso in G

S=

Trova un cammino S-aumentante P tale che S ∆ VP è estremale

Aumenta S

Itera


Università degli Studi di Roma Tor Vergata Facoltà di Ingegneria Corso di Laurea in Ingegneria dei...

Documents

Transcript of Università degli Studi di Roma Tor Vergata Facoltà di Ingegneria Corso di Laurea in Ingegneria dei...