Taglio minimo randomizzato - algoritmo di Karger

Metodo: Monte Carlo a errore unilaterale ripetuto (Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione →), con prodotto di probabilità condizionate (Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →) e union bound (Union bound e verifica randomizzata - identità polinomiali e prodotti di matriciSpazi discreti richiamati; inclusione-esclusione (con le troncate di Bonferroni) e union bound Pr[unione] ≤ somma, valido senza indipendenza e stretto quando gli eventi sono rari (collisioni: C(n,2)/m). Principio delle decisioni differite: si fissa tutto tranne una scelta casuale e si limita la probabilità su quella. Lemma di Schwartz-Zippel: un polinomio non nullo di grado totale d, valutato in un punto di S^n scelto uniformemente, si annulla con prob ≤ d/|S| (induzione sul numero di variabili); test di identità polinomiale con errore unilaterale, ripetuto (d/|S|)^k. Freivalds: per verificare AB=C si controlla A(Br)=Cr con r in {0,1}^n in tempo O(n^2), errore ≤ 1/2 (stretto), 2^-k con k prove. Fingerprint: due stringhe di n bit si confrontano con a mod p per un primo casuale p ≤ M, errore ≤ n/π(M).Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici →). Grafi: Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →, Rappresentazione dei grafiStrutture di base (lista dei vertici LV, lista degli archi LE), liste di adiacenza, matrice di adiacenza; operazioni incidentEdges, opposite, areAdjacent; spazio e tempi a confronto; esempio con un grafo di 5 vertici.Rappresentazione dei grafi →.

1. Il problema

Sia $G=(V,E)$ un multigrafo non orientato connesso (sono ammessi archi paralleli) con $n=|V|$ vertici. Un taglio è una partizione $V=S\cup(V\setminus S)$ con $S\ne\emptyset$ e $S\ne V$; la sua dimensione è il numero di archi con un estremo per parte. Il taglio minimo (globale, senza sorgente e pozzo) è quello di dimensione minima $k$: indica quanti archi bisogna togliere per sconnettere il grafo. Si può calcolare con algoritmi di flusso massimo; l'algoritmo di Karger ottiene lo stesso risultato con un'idea molto più semplice.

2. L'algoritmo di contrazione

Definizione. Contrarre un arco $e=\{u,v\}$ significa fondere $u$ e $v$ in un unico supervertice: gli archi paralleli a $e$ diventano cappi e si eliminano, gli altri archi restano (anche se diventano paralleli tra loro). Il numero di vertici scende di $1$.

Algoritmo (Karger). Finché il multigrafo ha più di $2$ vertici: scegliere un arco uniformemente tra gli archi rimasti e contrarlo. Restituire gli archi che collegano i due supervertici finali.

Ogni supervertice rappresenta un insieme di vertici originali; al termine i due supervertici sono una partizione $(S,V\setminus S)$ di $V$ e gli archi rimasti sono esattamente gli archi di $G$ che attraversano il taglio. L'algoritmo restituisce sempre un taglio valido (quindi di dimensione $\ge k$): è un Monte Carlo a errore unilaterale, che sbaglia solo restituendo un taglio non minimo. Con la matrice di adiacenza una contrazione costa $O(n)$ e l'intera esecuzione $O(n^2)$.

Esempio. Due triangoli collegati da un ponte: vertici $1,2,3,4,5,6$, archi $a=12$, $b=13$, $c=23$, $d=45$, $e=46$, $f=56$ e il ponte $g=34$. Il taglio minimo è $\{g\}$, di dimensione $k=1$, con $S=\{1,2,3\}$.

Esecuzione che riesce. Le scelte casuali sono $a$, poi $b$, poi $d$, poi $e$:

1. $7$ archi, $6$ vertici. Si contrae $a$: nasce $\{12\}$; $b$ e $c$ diventano due archi paralleli $\{12\}\text{-}3$. Restano $6$ archi.
2. Si contrae uno dei due archi paralleli (per esempio $b$): nasce $\{123\}$ e l'altro parallelo diventa un cappo, eliminato. Restano $4$ archi: il ponte $g$ ($\{123\}\text{-}4$), $d$, $e$, $f$.
3. Si contrae $d$: nasce $\{45\}$; restano $g$ ($\{123\}\text{-}\{45\}$) ed $e,f$ ($\{45\}\text{-}6$): $3$ archi.
4. Si contrae $e$: nasce $\{456\}$ e $f$ diventa un cappo. Resta il solo arco $g$ tra $\{123\}$ e $\{456\}$: taglio di dimensione $1$, il minimo.

Esecuzione che fallisce. Se il primo arco scelto è il ponte $g$ (probabilità $1/7$), le due metà si fondono e ogni taglio che si potrà ottenere ha almeno $2$ archi: il taglio minimo è perso.

3. Probabilità di successo

Teorema. Sia $C$ un taglio minimo di $G$ e $k=|C|$. L'algoritmo restituisce proprio $C$ con probabilità $$\Pr[\text{output}=C]\ \ge\ \frac2{n(n-1)}=\frac1{\binom n2}.$$

Dimostrazione. (1) Quando $C$ sopravvive. Gli archi tra le due parti di $C$ sono esattamente gli archi di $C$. Se nessun arco di $C$ viene mai contratto, ogni contrazione fonde due vertici della stessa parte, quindi ogni supervertice sta tutto in una parte; alla fine i due supervertici coprono $V$ e le due parti sono non vuote, dunque sono proprio le due parti di $C$ e l'output è $C$. Viceversa, se si contrae un arco di $C$ l'output non può essere $C$. Quindi basta stimare la probabilità che ai passi $i=1,\dots,n-2$ si scelga un arco fuori da $C$: sia $E_i$ l'evento «al passo $i$ non si sceglie un arco di $C$».

(2) Un passo. Si supponga che $E_1,\dots,E_{i-1}$ siano accaduti. Il multigrafo corrente $G_i$ ha $n_i=n-i+1$ vertici e $C$ è ancora un taglio di $G_i$ (con $k$ archi). Ogni taglio di $G_i$ è anche un taglio di $G$ con lo stesso numero di archi, quindi il taglio minimo di $G_i$ è ancora $k$. Il grado di ogni supervertice è $\ge k$ (gli archi uscenti da un supervertice formano un taglio), perciò $$|E_i|=\tfrac12\sum_v\deg(v)\ \ge\ \frac{n_ik}2 .$$ Si sceglie un arco di $C$ con probabilità $k/|E_i|\le2/n_i$, quindi $$\Pr[E_i\mid E_1\cap\dots\cap E_{i-1}]\ \ge\ 1-\frac2{n_i}=\frac{n-i-1}{n-i+1}.$$

(3) Prodotto. Per la regola del prodotto (Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →) $$\Pr\Big[\bigcap_{i=1}^{n-2}E_i\Big]\ge\prod_{i=1}^{n-2}\frac{n-i-1}{n-i+1}=\frac{n-2}{n}\cdot\frac{n-3}{n-1}\cdot\frac{n-4}{n-2}\cdots\frac24\cdot\frac13=\frac{2}{n(n-1)} ,$$ perché è un prodotto telescopico: restano a numeratore $2\cdot1$ e a denominatore $n(n-1)$. $\square$

Sull'esempio dei due triangoli ($n=6$, $k=1$) la dimostrazione si legge passo per passo. Il bound è $\frac23\cdot\frac35\cdot\frac12\cdot\frac13=\frac1{15}$; nell'esecuzione sopra la probabilità effettiva di evitare il ponte in ciascun passo è $\frac67,\frac56,\frac34,\frac23$, tutte più grandi dei fattori $1-2/n_i=\frac23,\frac35,\frac12,\frac13$.

Il valore esatto di successo per questo grafo, calcolato con Python enumerando tutte le sequenze di contrazioni con frazioni, è $13/35=0{,}371$; una simulazione con $10^5$ esecuzioni dà $0{,}370$. Il bound $1/15=0{,}067$ è molto pessimistico, ma è valido per ogni grafo.

Il bound è stretto. Sul ciclo $C_n$ ogni contrazione dà un ciclo più corto e alla fine restano due archi paralleli: l'output ha sempre dimensione $2$ ed è sempre un taglio minimo. I tagli minimi sono le coppie di archi, $\binom n2$ in tutto, e per simmetria (gli archi sopravvissuti sono una coppia uniforme) ciascuno esce con probabilità esattamente $1/\binom n2$. Con Python: $C_5$ dà $1/10$, $C_6$ dà $1/15$ per ognuno dei tagli. Per il grafo completo $K_4$ ($k=3$, quattro tagli minimi a vertice singolo) ognuno ha probabilità $1/5\ge1/6$.

Corollario. Un grafo con $n$ vertici ha al più $\binom n2$ tagli minimi.

Dimostrazione. Gli eventi «l'output è $C$» per tagli minimi distinti sono disgiunti, ciascuno ha probabilità $\ge1/\binom n2$ e la somma non supera $1$. $\square$

4. Ripetizioni

Un'esecuzione fallisce con probabilità $\le1-1/\binom n2$. Si eseguono $t$ esecuzioni indipendenti e si tiene il taglio più piccolo: fallisce solo se falliscono tutte, $$\Pr[\text{fallimento}]\le\Big(1-\frac1{\binom n2}\Big)^t\le e^{-t/\binom n2}.$$ Con $t=\binom n2$ il fallimento è $\le e^{-1}=0{,}368$ (esattamente $0{,}364$ per $n=10$, $0{,}368$ per $n=100$); con $t=\binom n2\ln n$ è $\le1/n$; in generale $t=\lceil\binom n2\ln(1/\delta)\rceil$ garantisce fallimento $\le\delta$. Per $\delta=0{,}01$: $n=10$ servono $\lceil45\ln100\rceil=208$ esecuzioni, $n=50$ servono $5642$, $n=100$ servono $22796$. Per il grafo dei due triangoli bastano $10$ ripetizioni, perché $(22/35)^{10}=0{,}0096$. Il costo totale con la matrice di adiacenza è $O(n^4\log n)$.

import random

def karger(archi, n):
    """Una esecuzione. archi: lista di coppie (u, v) con vertici 0..n-1. Restituisce la dimensione del taglio."""
    padre = list(range(n))
    def trova(x):
        while padre[x] != x:
            padre[x] = padre[padre[x]]
            x = padre[x]
        return x
    vertici = n
    while vertici > 2:
        u, v = random.choice(archi)                    # arco uniforme fra tutti...
        a, b = trova(u), trova(v)
        if a != b:                                      # ...scartando i cappi equivale a scegliere fra i non-cappi
            padre[a] = b
            vertici -= 1
    return sum(1 for u, v in archi if trova(u) != trova(v))

def taglio_minimo(archi, n, t):
    return min(karger(archi, n) for _ in range(t))

due_triangoli = [(0, 1), (0, 2), (1, 2), (3, 4), (3, 5), (4, 5), (2, 3)]
N = 100000
print(sum(karger(due_triangoli, 6) == 1 for _ in range(N)) / N)   # circa 13/35 = 0.371
print(taglio_minimo(due_triangoli, 6, 10))                          # 1 con prob >= 0.99

5. Karger-Stein in breve

Le prime contrazioni sono sicure (il rischio è concentrato alla fine, dove $n_i$ è piccolo): contrarre da $n$ a $t$ vertici preserva $C$ con probabilità $$\prod_{i=t+1}^{n}\Big(1-\frac2i\Big)=\frac{t(t-1)}{n(n-1)},$$ che per $t=\lceil1+n/\sqrt2\rceil$ è $\ge\frac12$ (per $n=100$: $t=72$ e $0{,}516$). L'algoritmo di Karger-Stein contrae fino a $t$ vertici due volte in modo indipendente e risolve ricorsivamente le due copie, tenendo il minimo; sotto $6$ vertici si fa tutto per forza bruta.

La probabilità di successo soddisfa $p(n)\ge1-\big(1-\tfrac12p(t)\big)^2=p(t)-p(t)^2/4$. Con $p_j$ la probabilità a profondità $j$ ($p_0=1$) si dimostra per induzione $p_j\ge1/(j+1)$: $\frac1j-\frac1{4j^2}\ge\frac1{j+1}$ equivale a $4j\ge j+1$. La profondità è $\log_{\sqrt2}n=2\log_2n$, quindi il successo è $\Omega(1/\log n)$. Il tempo soddisfa $T(n)=2T(n/\sqrt2)+O(n^2)$, cioè $O(n^2\log n)$ (teorema dell'esperto: $n^{\log_{\sqrt2}2}=n^2$, caso centrale; Algoritmi ricorsiviAlgoritmi ricorsivi come induzione eseguita; albero della ricorsione e record di attivazione nello stack; esempi ReverseArray, LinearSum, Power in tempo logaritmico, Fibonacci ricorsivo (esponenziale) e con memoizzazione; analisi della complessità con l'albero della ricorsione e correttezza per induzione.Algoritmi ricorsivi →). Ripetendo $O(\log^2n)$ volte si ottiene il taglio minimo con alta probabilità in $O(n^2\log^3n)$, molto meglio dei $O(n^4\log n)$ di Karger semplice.

Domande d'esame

1. Dimostra che Karger trova un dato taglio minimo con probabilità $\ge2/(n(n-1))$. Vedi il teorema della sezione 3: grado minimo $\ge k$, $|E_i|\ge n_ik/2$, fattori $1-2/n_i$, prodotto telescopico.
2. Dimostra che un grafo ha al più $\binom n2$ tagli minimi. Eventi disgiunti «output $=C$», ciascuno con probabilità $\ge1/\binom n2$, somma $\le1$. Il ciclo $C_n$ raggiunge il limite.
3. Quante esecuzioni per un grafo con $n=20$ vertici se si vuole fallire con probabilità $\le1\%$? $\binom{20}2=190$ e $190\ln100=875{,}0$, quindi $t=875$.
4. Perché ogni supervertice ha grado almeno $k$? Gli archi uscenti da un supervertice separano quel supervertice dal resto: sono un taglio di $G$, quindi sono almeno $k$.