Esercizio - Contrazione di Karger a mano su un grafo con cinque vertici

Testo. Il grafo $G$ ha vertici $1,2,3,4,5$ e archi $12,\,13,\,23,\,24,\,34,\,45$.

1. Trovare la dimensione $k$ del taglio minimo e il limite inferiore di Karger sulla probabilità di trovarlo.
2. Eseguire l'algoritmo con le scelte $24$, poi un arco fra il supervertice e $3$, poi un arco fra $1$ e il supervertice: descrivere i multigrafi e il taglio finale.
3. Calcolare la probabilità esatta che una esecuzione trovi il taglio minimo, distinguendo il primo arco scelto.
4. Quante esecuzioni indipendenti per fallire con probabilità $\le1\%$: col valore esatto e col limite di Karger?

Teoria: Taglio minimo randomizzato - algoritmo di KargerTaglio minimo globale di un multigrafo con n vertici. Algoritmo di Karger: finché restano più di 2 vertici, scegliere un arco uniformemente tra i rimasti e contrarlo (fondere gli estremi, tenere i paralleli, togliere i cappi); gli archi tra i due supervertici finali sono un taglio. Un taglio minimo C di k archi sopravvive se nessun suo arco viene contratto; con n_i vertici il grado minimo è ≥ k, quindi |E_i| ≥ n_i k/2 e Pr[contrarre un arco di C] ≤ 2/n_i; il prodotto telescopico dà Pr[output = C] ≥ 2/(n(n-1)) = 1/C(n,2). Con t = C(n,2) ln(1/δ) ripetizioni indipendenti il fallimento è ≤ δ. Corollario: un grafo ha al più C(n,2) tagli minimi (stretto per il ciclo). Karger-Stein: contrarre fino a n/√2+1 vertici (sopravvive con prob ≥ 1/2) e ricorrere due volte, T(n) = O(n² log n), successo Ω(1/log n).Taglio minimo randomizzato - algoritmo di Karger →.

Soluzione

Punto 1. Il vertice $5$ ha grado $1$, quindi $\{45\}$ è un taglio di dimensione $1$ e $k=1$ (il grafo è connesso: $k\ge1$). È l'unico taglio minimo: ogni altro taglio ha almeno $2$ archi, perché il sottografo su $\{1,2,3,4\}$ ha taglio minimo $2$ (ai vertici $1$ e $4$ arrivano due archi). Con $n=5$ il limite è $\frac2{5\cdot4}=\frac1{10}$.

Punto 2. Scelte: $24$, poi $w3$, poi $1V$.

1. Contrae $24$: nasce $w=\{2,4\}$. Gli archi diventano $12\to1w$, $13$, $23\to w3$, $34\to3w$, $45\to w5$: $5$ archi ($1w$, $13$, due paralleli $w3$, $w5$), $4$ vertici $\{1,w,3,5\}$.
2. Contrae un arco $w3$: nasce $V=\{2,3,4\}$ e l'altro $w3$ diventa un cappo, eliminato. Archi: $1V$ (da $1w$), $1V$ (da $13$), $V5$ (da $w5$): $3$ archi, $3$ vertici $\{1,V,5\}$.
3. Contrae uno dei due $1V$: nasce $U=\{1,2,3,4\}$; l'altro diventa un cappo. Resta il solo arco $U5$.

Il taglio finale è $\{U,5\}$, cioè l'arco $45$, di dimensione $1$: il taglio minimo è trovato.

Punto 3. Il primo arco ha probabilità $1/6$ ciascuno; se è $45$ il taglio è perso. Si calcola la probabilità $s$ di non scegliere mai $45$ in ciascun caso.

• Primo arco $12$ (o $13$, per simmetria $2\leftrightarrow3$). Nasce $w$; archi: $w3$ doppio, $w4$, $34$, $45$: $5$ archi. Si evita $45$ con $4/5$:

  • $w3$ ($2/5$): nasce $\{1,2,3\}$ con archi $\to4$ doppi e $45$: $3$ archi, evita $45$ con $2/3$;
  • $w4$ ($1/5$): nasce $\{1,2,4\}$ con archi $\to3$ tripli e $\to5$: $4$ archi, evita con $3/4$;
  • $34$ ($1/5$): nasce $\{3,4\}$ con archi $w\{3,4\}$ tripli e $\{3,4\}5$: $4$ archi, evita con $3/4$.

  $s=\frac25\cdot\frac23+\frac15\cdot\frac34+\frac15\cdot\frac34=\frac4{15}+\frac3{10}=\frac{17}{30}$.

• Primo arco $23$. Nasce $w=\{2,3\}$; archi: $1w$ doppio, $w4$ doppio, $45$: $5$ archi. Con $1w$ ($2/5$) o $w4$ ($2/5$) si ottengono $3$ archi (due paralleli e $45$) e si evita $45$ con $2/3$: $s=\frac45\cdot\frac23=\frac8{15}$.

• Primo arco $24$ (o $34$, per simmetria). Nasce $w=\{2,4\}$; archi: $1w$, $13$, $w3$ doppio, $w5$: $5$ archi, da cui evitare $w5$ ($4/5$ in tutto):

  • $1w$ ($1/5$): $\{1,w\}$ con $\to3$ tripli e $\to5$: $3/4$;
  • $13$ ($1/5$): $\{1,3\}$ con $\to w$ tripli e $w5$: $3/4$;
  • $w3$ ($2/5$): $\{w,3\}$ con $\to1$ doppi e $\to5$: $2/3$.

  $s=\frac15\cdot\frac34+\frac15\cdot\frac34+\frac25\cdot\frac23=\frac3{10}+\frac4{15}=\frac{17}{30}$.

Probabilità totale: $$\Pr[\text{successo}]=\frac16\Big(\underbrace{\tfrac{17}{30}+\tfrac{17}{30}}_{12,\,13}+\tfrac8{15}+\underbrace{\tfrac{17}{30}+\tfrac{17}{30}}_{24,\,34}+0\Big)=\frac16\cdot\frac{68+16}{30}=\frac{84}{180}=\frac7{15}=0{,}467 .$$ Il limite $1/10$ è molto pessimistico.

Punto 4. Fallimento per esecuzione $1-\frac7{15}=\frac8{15}$. Serve $(8/15)^t\le0{,}01$: $t\ge\frac{\ln0{,}01}{\ln(8/15)}=\frac{-4{,}605}{-0{,}629}=7{,}33$, quindi $t=8$. Con il limite di Karger: $t=\lceil\binom52\ln100\rceil=\lceil46{,}05\rceil=47$.

Risultati: $k=1$ (arco $45$); limite $0{,}1$; probabilità esatta $7/15$; $8$ esecuzioni (esatto) o $47$ (limite).

import random
G = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5)]
def karger(archi, vertici):
    padre = {v: v for v in vertici}
    def trova(x):
        while padre[x] != x: x = padre[x]
        return x
    n = len(vertici)
    while n > 2:
        u, v = random.choice(archi)
        a, b = trova(u), trova(v)
        if a != b: padre[a] = b; n -= 1
    return sum(trova(u) != trova(v) for u, v in archi)
N = 200000
print(sum(karger(G, range(1, 6)) == 1 for _ in range(N)) / N, 7 / 15)    # 0.467