Esercizio - Probabilità esatte di Karger sul ciclo e sul grafo completo

Testo. Si considera l'algoritmo di contrazione di Karger.

1. Sul ciclo $C_5$ (vertici $1,\dots,5$, archi $12,23,34,45,51$) calcolare la probabilità che esca un taglio minimo specifico, per esempio la coppia $\{12,34\}$. Confrontarla col limite $1/\binom n2$.
2. Sul grafo completo $K_4$ calcolare la probabilità che esca il taglio $\{d\}$ (vertice $d$ da solo) e quella che esca un taglio minimo qualunque.
3. Quante esecuzioni indipendenti servono su $K_4$ per fallire con probabilità $\le1\%$? Quante darebbe il limite generale?
4. (Verifica con un programma) Probabilità esatte su $K_5$.

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 → (sezione sulla stretta del limite).

Soluzione

Punto 1. Nel ciclo ogni vertice ha grado $2$ e, dopo ogni contrazione, il grafo resta un ciclo (più corto) che ha $n_i$ vertici e $n_i$ archi. Il taglio minimo vale $k=2$ e in ogni passo $|E_i|=n_i=\frac{n_ik}{2}$: la disuguaglianza $|E_i|\ge n_ik/2$ della dimostrazione è un'uguaglianza. Quindi la probabilità di non scegliere un arco di $C=\{12,34\}$ al passo $i$ vale esattamente $1-\frac2{n_i}$ (e il taglio specifico è un taglio minimo del ciclo contratto). I passi sono $n_i=5,4,3$: $$\Pr[\text{output}=C]=\Big(1-\frac25\Big)\Big(1-\frac24\Big)\Big(1-\frac23\Big)=\frac35\cdot\frac12\cdot\frac13=\frac1{10}=\frac1{\binom52}.$$ Il limite è raggiunto: nel ciclo è la probabilità esatta di ciascuno dei $\binom52=10$ tagli minimi (le coppie di archi), e la somma è $10\cdot\frac1{10}=1$: l'output è sempre un taglio minimo.

Punto 2. In $K_4$ ogni vertice ha grado $3$, $k=3$, $n=4$, il limite è $\frac1{6}$. Per ottenere $\{d\}$ non si deve mai contrarre un arco incidente a $d$.

• Primo passo: $6$ archi, $3$ incidenti a $d$: si evita con $\frac36=\frac12$. Si contrae, per esempio, $ab$: nasce $w=\{a,b\}$.
• Secondo passo: il multigrafo ha vertici $w,c,d$ e archi $wc$ (doppio: $ac$, $bc$), $wd$ (doppio: $ad$, $bd$), $cd$ (singolo): $5$ archi. Si evita $d$ solo contraendo $wc$: probabilità $\frac25$.
• Alla fine restano $\{w,c\}$ e $d$, con $3$ archi: il taglio $\{d\}$.

$$\Pr[\text{output}=\{d\}]=\frac12\cdot\frac25=\frac15=0{,}2\ \ge\ \frac16 .$$ Per simmetria vale lo stesso per ciascuno dei $4$ tagli a vertice singolo (i soli tagli minimi, di dimensione $3$); i tagli $2+2$ hanno $4$ archi. Probabilità di un taglio minimo qualunque: $4\cdot\frac15=\frac45$. Si verifica anche direttamente: all'ultimo passo, con vertici $w,c,d$ e archi $2,2,1$, il taglio finale ha dimensione $3$ se si contrae $wc$ o $wd$ ($\frac25+\frac25=\frac45$) e dimensione $4$ se si contrae $cd$ ($\frac15$).

Punto 3. Un'esecuzione fallisce (non trova un taglio minimo) con probabilità $\frac15$. Serve $(1/5)^t\le0{,}01$, $t\ge\frac{\ln100}{\ln5}=\frac{4{,}605}{1{,}609}=2{,}86$, quindi $t=3$ ($0{,}008$). Il limite generale darebbe $t=\lceil\binom42\ln100\rceil=\lceil27{,}6\rceil=28$.

Punto 4. In $K_5$ ogni vertice ha grado $4$, quindi $k=4$ e i tagli minimi sono i cinque a vertice singolo (un taglio $2+3$ ha $6$ archi). A mano, per il taglio $\{e\}$:

• primo passo: $10$ archi, $4$ incidenti a $e$, si evita $e$ con $\frac6{10}=\frac35$; per simmetria si contrae $ab$ e nasce $w$;
• secondo passo: archi $wc,wd,we$ doppi e $cd,ce,de$ singoli, $9$ in tutto; quelli che non toccano $e$ sono $wc$ ($2$), $wd$ ($2$), $cd$ ($1$);
• terzo passo, se si è contratto $wc$ (probabilità $\frac29$): nasce $\{a,b,c\}$ con $3$ archi verso $d$, $3$ verso $e$ e l'arco $de$, $7$ archi; si evita $e$ solo con i $3$ verso $d$: $\frac37$. Lo stesso se si è contratto $wd$ ($\frac29$);
• terzo passo, se si è contratto $cd$ ($\frac19$): nasce $\{c,d\}$ con $4$ archi verso $w$, mentre $w$ ha $2$ archi verso $e$ e $\{c,d\}$ altri $2$: su $8$ archi, $4$ evitano $e$, cioè $\frac12$.

$$\Pr[\text{output}=\{e\}]=\frac35\Big(\frac49\cdot\frac37+\frac19\cdot\frac12\Big)=\frac35\cdot\frac{31}{126}=\frac{31}{210}=0{,}1476\ \ge\ \frac1{10}.$$ Un taglio minimo qualunque esce con $5\cdot\frac{31}{210}=\frac{31}{42}=0{,}738$. Il programma sotto enumera tutte le sequenze di contrazioni con le frazioni e conferma $\frac{31}{210}$, oltre a $\frac1{10}$ per ciascuno dei $10$ tagli di $C_5$ e $\frac15$ per i $4$ di $K_4$.

Risultati: $C_5$: $1/10$ (limite raggiunto); $K_4$: $1/5$ per taglio, $4/5$ in totale, $t=3$; $K_5$: $31/210$ per taglio.

from fractions import Fraction as F
from functools import lru_cache
from collections import Counter
from itertools import combinations

def esatto(archi):
    """Distribuzione esatta del taglio finale di Karger: {lato che contiene il vertice minimo: probabilita'}."""
    @lru_cache(maxsize=None)
    def rec(stato):                                   # stato: ((A, B), molteplicita') con A, B frozenset
        lati = {x for (a, b), _ in stato for x in (a, b)}
        if len(lati) == 2:
            return {min(lati, key=sorted): F(1)}
        tot = sum(m for _, m in stato)
        out = Counter()
        for (a, b), m in stato:
            nuovo = Counter()
            for (c, d), mm in stato:
                if {c, d} == {a, b}: continue         # il cappo scompare
                c2 = a | b if c in (a, b) else c
                d2 = a | b if d in (a, b) else d
                nuovo[tuple(sorted((c2, d2), key=sorted))] += mm
            for lato, p in rec(tuple(sorted(nuovo.items(), key=lambda kv: [sorted(x) for x in kv[0]]))).items():
                out[lato] += F(m, tot) * p
        return dict(out)
    c = Counter(tuple(sorted((frozenset([u]), frozenset([v])), key=sorted)) for u, v in archi)
    return rec(tuple(sorted(c.items(), key=lambda kv: [sorted(x) for x in kv[0]])))

dim = lambda E, lato: sum((u in lato) != (v in lato) for u, v in E)
for nome, E in (("C5", [(i, i % 5 + 1) for i in range(1, 6)]), ("K4", list(combinations(range(1, 5), 2))),
                ("K5", list(combinations(range(1, 6), 2)))):
    d = esatto(E); k = min(dim(E, l) for l in d)
    minimi = {tuple(sorted(l)): p for l, p in d.items() if dim(E, l) == k}
    print(nome, k, set(minimi.values()), sum(minimi.values()))     # C5 {1/10} 1;  K4 {1/5} 4/5;  K5 {31/210} 31/42