Il problema del minimo albero ricoprente

in un grafo con archi privati

Un problema molto noto…

INPUT: G=(V,E): grafo non diretto pesato, w(e)R+ per ogni e E

T è un albero ricoprente di G se:1. T è un albero2. T è un sottografo di G3. T contiene tutti i nodi di G

OUTPUT: T=(V,ET) minimo albero ricoprente di

G, ovvero che minimizza il peso totale w(T)= w(e)

e ET

Scenario

Archi di un grafo controllati da agenti egoistici Solo l’agente conosce il peso associato al

proprio arco Obiettivo: calcolare una “buona” soluzione di

un certo problema di ottimizzazione rispetto a pesi reali

Strumento: progettazione di un meccanismo truthful (pagamento opportuno degli agenti per convincerli a dire la verità!)

Il problema del minimum spanning tree (MST) egoistico

Input: un grafo G=(V,E), ogni arco è un agente egoistico, un nodo sorgente s e un nodo destinazione t; il tipo di un agente è il costo di utilizzo dell’arco (quindi tipo > 0); la sua valutazione è uguale al suo tipo;

SCF: un vero MST di G=(V,E,tipi).

Più Formalmente Soluzioni ammissibili:

F: insieme degli alberi ricoprenti di G Tipo dell’agente e:

e: peso dell’arco intuitivamente: e è il costo che l’agente

sostiene per utilizzare e Valutazione agente e di un albero

ricoprente TF : ve(e,T)= e se eE(T), 0 altrimenti

SCF: minimo albero ricoprente di G=(V,E,)

Come progettare un meccanismo truthful per il

problema?Osservazione cruciale:

il (vero) peso di un albero ricoprente T è:

eE ve(e,T)

problema utilitario!

…usiamo i meccanismi VCG

Meccanismo VCG

M= <g(r), p(x)>: g(r): arg minxF j vj(rj,x)

pe(x): Per ogni arco eE:

pe =j≠e vj(rj,g(r-e)) -j≠e vj(rj,x) cioè

Meccanismo VCG M= <g(r), p(x)>:

g(r): dato il grafo G e le dichiarazioni r=(r1,…,rm), calcola il MST T=(V,ET) di G=(V,E,r)

pe: Per ogni arco e E, pe =j≠e vj(rj,x(r-e)) -j≠e vj(rj,x) cioè

pe=w(TG-e)-w(T)+ re se eET,

pe=0 altrimenti.

dove TG-e è il MST di rimpiazzo per e (MST di G-e=(V,E\{e},r-e))

Ipotesi di lavoro: Grafo 2-edge connesso (altrimenti TG-e potrebbe non esistere

il possessore dell’arco e “terrebbe in pugno” il sistema!)

Quel è la complessità temporale del meccanismo?

…dobbiamo calcolare con un MST di G

…e il pagamento per gli archi selezionati

Miglior algoritmo centralizzato richiede tempo O(m (m,n))

Una soluzione banale

e T applichiamo l’algoritmo di calcolo dell’MST al grafo G-e

Complessità: n-1 archi dell’MST per O(m (m,n)): O(nm (m,n))

La soluzione efficiente che proponiamo costerà ancora O(m (m,n))!!!

La funzione di Ackermann A(i,j) e la sua inversa (m,n)

A(i,j) per piccoli valori di i e j

2 23 24

22

22

222222

222222

22222

216

22

22

2

216

22

22

2

222

2 16

... ..

... ..

..

..

j=1 j=2 j=3 j=4

i=1

i=2

i=3

La funzione (m,n)

Proprietà

1. Fissato n, (m,n) è monotonicamente decrescente al crescere di m

(m,n)= min {i>0 : A(i, m/n) > log2 n}

crescente in m

2. (n,n) per n

(n,n)= min {i>0 : A(i, n/n) > log2 n} = min {i>0 : A(i, 1) > log2 n}

(m,n) 4 per ogni scopo pratico (cioè per valori di n ragionevoli)

A(4,m/n) A(4,1) = A(3,2)

=22

2 16.. .

>> 1080

numero stimato di atomi nell’universo osservabile

(m,n)= min {i>0 : A(i, m/n) > log2 n}

Osservazione

quindi (m,n) 4 per ogni n<21080

Un po’ di storia

1926: Boruvka riscoperto da: Choquete, 1938 Florek et. al., 1951 Sollin, 1961 (l’articolo di

Boruvka era ormai conosciuto!)

1930: Jarnìk riscoperto da: Prim, 1957 Dijkstra, 1959

1956: Kruskal riscoperto da: Loberman e Weinberg,

1956, qualche mese dopo

…e le complessità temporali di

questi algoritmi?

…raramente menzionatenegli articoli…

Esempi:Quick Sort è del ’61, Hoare

Heap binari del ’64, Williams

Complessità temporali 1975: Yao - O(m loglogn)

linear time selection di Blum et al. (1972) 1975: Johnson O(m logd n)

d=max{m/n,2} d-heaps (Johnson 1975)

1976: Cheriton e Tarjan – O(m log logd n) Mergeable leftist heaps di Crane (1972)

1984: Fredman e Tarjan – O(m log*(m,n)) Heap di Fibonacci di Fredman e Tarjan (1984)

1986: Gabow, Galil, Spencer, Tarjan – O(mloglog*(m,n))

Usando meglio gli heap di Fibonaccilog*(m,n)= 1+log*n-log*(m/n)

…tutti usano un approccio greedy…

Perché l’approccio greedy: una proprietà forte

Dato G=(V,E), grafo non orientato

F = {FE: F non contiene cicli}

(E, F ): matrioide grafico

Complessità temporali 1997: Chazelle - O(m (m,n) log (m,n))

Soft-heap di Chazelle (1997) 2000: Chazelle O(m (m,n))

Miglior uso dei Soft-heap 2002: Pettie e Ramachandran –

O(MST*(m,n)) dove MST*(m,n): complessità dell’albero di

decisione del problema del minimo albero ricoprente (numero minimo di confronti nel caso peggiore)

MST*(m,n)= O(m (m,n)) e MST*(m,n)= (m)

Un problema aperto

MST*(m,n) = O(m)?

Un problema correlato: verifica di un MST

Input: grafo G=(V,E) pesato non orientato, T=(V,ET) albero ricoprente di G

Domanda: T è un MST per G?

Verifica di un MST

6

2

7

1

9

3

5

4

10

8

13

11

Un altro problema correlato: l’analisi di

sensitività degli archi di un MST

Input grafo G=(V,E) pesato non orientato T=(V,ET) minimo albero ricoprente di G

Domanda quanto possono aumentare i pesi w(e) (e

E) prima di inficiare la minimalità di T?

Esempio: arco non in T

66

2

7

1

9

3

10

4

10

8

13

11

Esempio: arco in T

86

2

7

1

9

3

10

4

10

8

13

11

Sulla complessità dei problemi

Verifica analisi disensitività

calcoloMST

riduce linearmente riduce linearmente

O(m)(m) eO(m (m,n))O(m log(m,n))

Notazioni

G=(V,E), T albero ricoprente di G. Definiamo:

Per ogni f=(x,y) E\E(T) T(f): (unico) cammino semplice in T che

unisce x e y Per ogni e E(T)

C(e)={f E\E(T): e T(f)}

Dim (per assurdo): Sia e l’arco più pesante in un ciclo C={e }P, e supponiamo e T

e e’ T

T’=T \ {e} {e’}

w(e’) < w(e) w(T’) < w(T)

T non è MST(G)

X

V\X

P

Proprietà dei cicliTeorema: Sia G=(V,E) un grafo non orientato e pesato, sia e l’arco più pesante di un qualsiasi ciclo in G. Allora e MST(G)

Proprietà dei tagli

G=(V,E) grafo non orientato e pesatoX V un qualsiasi sottoinsieme di

verticie arco più leggero che attraversa il

taglio (X,V\X), allora

e MST(G)

DimSia e l’arco più leggero del taglio (X,V\X). Sia

T=MST(G), e supponiamo e T, facciamo vedere che T MST(G)

e

e’

e : arco più leggero del taglio

w(e) < w(e’) w(T’) < w(T)T(e)

T(e): cammino in T che uniscegli estremi di eT’=T \ {e’} {e}

T non è MST(G)

X V\X

Condizione di minimalità di un MST

Corollario G=(V,E) grafo non diretto, connesso,

pesato T albero ricoprente di G. allora T è minimo se e soltanto se per ogni arco

f non dell’albero vale: w(f) w(e) per ogni e in T(f)

…quindi…

Se f è un arco non dell’albero T rimane minimo finché w(f) non scende

sotto w(e), dove e è l’arco più pesante in T(f); chiamiamo tale valore down(f)

Se e è un arco dell’albero T rimane minimo finché w(e) non cresce

oltre w(f), dove f è l’arco più leggero tale che e T(f) (f è chiamato arco di swap per e); chiamiamo tale valore up(e)

…più formalmente…

Fare analisi di sensitività vuol dire calcolare:

Per ogni f E\E(T): down(f )= maxe T(f) w(e)

Per ogni e E(T) up(e)= minf C(e) w(f) swap(e)= arg minf C(e) w(f)

Analisi di sensitività

down(f)=66

2

7

1

9

3

10

4

10

8

13

11

f

T(f)

Analisi di sensitività degli archi del MST

up(e)=86

2

7

1

9

3

10

4

10

8

13

11

e

C(e)

Osservazione

Calcolare tutti i valori up(e) è equivalente a calcolare il peso di un MST di G-e per ogni e di T; infatti

w(TG-e)=w(T)-w(e)+up(e)

Nel meccanismo VCG il pagamento pe di un arco e della soluzione è esattamente pari ad up(e)!!

Idea dell’algoritmo efficiente

Per ogni e E(T) guardare efficientemente tutti gli archi che formano un ciclo con e e prendere il minimo (up(e))

Per ogni f E\E(T) guardare efficientemente tutti gli archi in T(f) e prendere il massimo (down(e))

Il Transmuter Dato G=(V,E) e un suo albero ricoprente T, un

transmuter è un grafo diretto aciclico D che rappresenta in modo compatto l’insieme dei cicli fondamentali di G rispetto a T, ovvero l’insieme {T(f) : f arco non dell’albero}

D conterrà:1. Una sorgente (nodo con grado entrante nullo) s(e) per

ogni arco e di T2. Un pozzo (nodo con grado uscente nullo) t(f) per ogni

arco f non in T3. Un certo numero di nodi ausiliari con grado entrante pari

a 2 e grado uscente diverso da zero. Proprietà fondamentale: c’è un cammino in D

da una data sorgente s(e) a un pozzo t(f) se e solo se e T(f)

Un esempio

Come si costruisce un transmuter

Tarjan ha mostrato che ad ogni albero ricoprente di un grafo può essere associato un transmuter con O(m (m,n)) nodi ed archi, il quale può essere calcolato in tempo O(m (m,n))

La costruzione è un’estensione delle tecniche usate per mantenere efficientemente insiemi di foreste disgiunte sottoposte a operazioni di LINK e operazioni di EVAL

R. E. Tarjan, Application of path compression on balanced trees, J. ACM 26 (1979) pp 690-715

Ordinamento topologico

D=(N,A) grafo diretto. Un ordinamento topologico di D è un ordinamento v1, v2, …,vn dei nodi tale che per ogni arco (vi, vj) A, vale i < j.

D ammette un ordinamento topologico se e solo se D è un DAG (grafo diretto aciclico).

Un ordinamento topologico dei nodi può essere trovato (se esiste) in tempo O(n+m).

Calcolo degli incrementi per gli archi dell’albero

Ordiniamo topologicamente il transmuter (che è un DAG)

Etichettiamo ogni nodo del transmuter con un valore reale processando i nodi in ordine topologico inverso: Etichettiamo ogni pozzo t(f) con il valore w(f)

(associamo al valore anche l’arco f ) Etichettiamo ogni nodo v che non è un pozzo con il

valore minimo fra i valori dei suoi (immediati) successori

Quando tutti i nodi sono etichettati ogni sorgente s(e) è etichettata con il valore up(e) (e relativo arco di swap)

2

5

3

6

4

9

7

8

96

11

10

7 7 6 6 9 10

7 6 10

7 8 9 6 10 11

Calcolo dei valori up(e)

Calcolo dei decrementi per gli archi non dell’albero

Etichettiamo ogni nodo del transmuter con un valore reale processando i nodi in ordine topologico Etichettiamo ogni sorgente s(e) con il valore w(e)

(associamo al valore anche l’arco e) Etichettiamo ogni nodo v che non è una sorgente

con il valore massimo fra i valori dei suoi (immediati) predecessori

Quando tutti i nodi sono etichettati ogni pozzo t(f) è etichettato con il valore down(f)

2

5

3

6

4

9

7

8

96

11

10

2 6 5 3 4 9

6 5 9

6 6 6 5 9 9

Calcolo dei valori down(f)

Complessità temporale

1. Costruzione Transmuter: O(m (m,n))2. Calcolo valori up(e) e down(f):

Trovare l’ordinamento topologico: O(m (m,n))Processare il transmuter: O(m (m,n))

Complessità computazionale del VCG

TeoremaIl meccanismo VCG per il problema del MST

può essere implementato in tempo O(m (m,n)).

DimComplessità di g(٠): O(m (m,n))Complessità di p(٠): calcolo tutti i valori up(e)

in tempo O(m (m,n)).