Il problema del minimo albero
ricoprente
in un grafo non cooperativo
Un problema molto conosciuto


1.
2.
3.
G=(V,E): grafo non diretto pesato, w(e) 
R+ per ogni e E (tipo privato dell’agente
che possiede l’arco e)
T è un albero ricoprente di G se:
T è un albero
T è un sottografo di G
T tocca tutti i nodi di G
Un problema molto conosciuto

Input:


grafo G=(V,E) pesato non orientato
Output:

T=(V,ET) albero ricoprente di G che minimizza il peso

w(e)
eE
totale w(T)=
T

Miglior algoritmo centralizzato richiede tempo
O(m (m,n))
La funzione di Ackermann (e
la sua inversa)
A(i,j) per piccoli valori di i e j
j=1
j=2
j=3
j=4
i=1
2
22
23
24
i=2
22
22 2
2
22
22 2
2
22
2
..
i=3
22
2
.2 16
.
.
2
2
22
2.
2
.
.
2
.. 16
2
..
22
2
2
2
..
2
2
2
16
La funzione (m,n)
Proprietà
1.
2.
3.
fissato n, (m,n) monotonicamente
decrescente al crescere di m
(n,n)  
per n  
(m,n)  4 per ogni scopo pratico
1.
(m,n)= min {i>0 : A(i, m/n) > log2 n}
crescente in m
Proprietà
2. (n,n)  
per n  
(n,n)= min {i>0 : A(i, n/n) > log2 n}
= min {i>0 : A(i, 1) > log2 n}


Proprietà
3. (m,n)  4 per ogni scopo pratico
(m,n)= min {i>0 : A(i, m/n) > log2 n}
A(4,m/n)  A(4,1) = A(3,2)
.2 16
.
.
=22
>> 1080
 numero stimato di atomi
nell’universo osservabile
Meccanismo VCG per il
problema del MST

M= <g(r), p(g(r))>



g(r): dato il grafo G e le dichiarazioni r=(r1,…,rm), calcola il
MST di G, T=(V,ET)
pe: Per ogni arco e  ET
pe=w(TG-e)-w(T)+ w(e)
(w(e): peso riportato per e)
Per ogni e  T dobbiamo calcolare TG-e, ovvero il MST di
rimpiazzo per e (MST in G-e =(V,E\{e}))
Ipotesi di lavoro: Grafo 2-edge connesso (altrimenti TG-e
potrebbe non esistere  il possessore dell’arco e
“tiene in pugno” il sistema!)
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))!!!
Una soluzione un po’ meno
banale




Proprietà dei tagli di un MST: sia (V’,V’’) un
taglio in G: allora, l’arco di peso minimo che
“attraversa” il taglio appartiene all’MST
TG-e coincide con T-e+f, dove f è l’arco di peso
minimo che attraversa il taglio indotto dalla
rimozione di e da T
Controlliamo gli O(m) archi del taglio
suddetto e troviamo f
Complessità: n-1 archi dell’MST per O(m):
O(m (m,n)+mn)=O(mn)
L’analisi di sensitività degli
archi dell’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  T)
prima di inficiare la minimalità di T?
Esempio
4
11
10
13
6
8
8
10
2
1
3
7
9
Notazioni
G=(V,E)
 T albero ricoprente di G
Definiamo
 Per ogni f=(x,y)  E\E(T)



T(f): (unico) cammino in T che unisce x e y
Per ogni e  E(T)

C(e)={f  E\E(T): e  T(f)}
Proprietà dei cicli


G=(V,E) grafo non orientato e pesato,
e l’arco più pesante in un qualsiasi ciclo
Allora e  MST(G)
Dim (per assurdo)
Sia e l’arco più pesante in un ciclo C={e }P,
e supponiamo e  T
X
P
e
V\X
T’=T \ {e}  {e’}
w(e’) < w(e)  w(T’) < w(T)
e’  T
T non è MST(G)
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 e è un arco dell’MST, esso rimane minimo
finché w(e) non cresce oltre w(f), dove f è
l’arco più leggero che forma un ciclo con e (f
è chiamato arco di swap per e); chiamiamo
tale valore up(e)
…più formalmente…

Per ogni e  E(T)


up(e)= minf  C(e) w(f)
swap(e)= arg minf  C(e) w(f)
Analisi di sensitività degli archi
dell’MST
C(e)
4
11
10
13
6
e
8
10
up(e)=8
2
1
3
7
9
Osservazioni

Calcolare tutti i valori up(e) (swap(e)) vuol
dire ricalcolare MST(G-e) per ogni e di T


MST(G-e)=MST(G) \{e}  {swap(e)}
Nel meccanismo VCG il pagamento pe di
un arco e della soluzione è esattamente
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))
Il Transmuter


1.
2.
3.

Dato G=(V,E) e un suo albero ricoprente T, un transmuter
è un grafo diretto aciclico D che rappresenta l’insieme dei
cicli fondamentali di G rispetto a T, ovvero l’insieme {T(f)
: f arco non dell’albero}
D contiene:
Una sorgente (nodo con grado entrante nullo) s(e) per
ogni arco e di T
Un pozzo (nodo con grado uscente nullo) t(f) per ogni
arco f non in T
Un numero arbitrario di nodi ausiliari
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)
Come si costruisce il
transmuter



Tarjan ha mostrato come costruire un transmuter
che ha O(m (m,n)) nodi 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
Alcuni richiami di base
D=(N, A) grafo diretto ( |N|=h )

Un ordinamento topologico è un
ordinamento dei nodi di D
v1, v2, …,vh
tale che:
per ogni arco (vi, vj) A, vale i < j

Alcuni richiami di base



D=(N, A) grafo diretto
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| + |A|) (visita in profondità)
Calcolo degli incrementi per gli
archi dell’albero




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)
Calcolo dei valori up(e)
7
2
8
5
6
9
7
4
7
7
7
8
11
6
9
10
6
6
6
9
3
10
9
10
6
10
11
Complessità

1.
2.
Tempo
Costruzione Transmuter: O(m (m,n))
Calcolo valori up(e):
Trovare ordinamento topologico O(m (m,n))
Processare il transmuter in O(m (m,n))

1.
Spazio
O(m (m,n))