Esercizio - Taglio grande e derandomizzazione sul grafo di Petersen

Teoria: Metodo probabilistico - valore atteso, alterazioni e derandomizzazioneMetodo probabilistico: se un oggetto casuale ha una proprietà con probabilità positiva (o una variabile ha media mu, quindi qualche esito la raggiunge) allora l'oggetto esiste; taglio di almeno |E|/2, MAX-SAT con 7/8, limite inferiore di Ramsey R(k,k) > 2^(k/2), alterazioni (insiemi indipendenti, Ramsey), derandomizzazione con le aspettative condizionate, lemma locale di Lovász solo enunciato.Metodo probabilistico - valore atteso, alterazioni e derandomizzazione → (taglio grande, aspettative condizionate), 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à →.

Testo. Il grafo di Petersen ha $10$ vertici $0,\dots,9$ e $15$ archi: il ciclo esterno $i\sim i+1\pmod5$ per $i=0,\dots,4$, i raggi $i\sim i+5$ e il pentagramma interno $5+i\sim5+((i+2)\bmod5)$. Le liste di adiacenza sono $0:\{1,4,5\}$, $1:\{0,2,6\}$, $2:\{1,3,7\}$, $3:\{2,4,8\}$, $4:\{3,0,9\}$, $5:\{0,7,8\}$, $6:\{1,8,9\}$, $7:\{2,5,9\}$, $8:\{3,6,5\}$, $9:\{4,7,6\}$.

1. Assegnando ogni vertice a caso a una delle due parti, calcolare il numero atteso di archi tagliati e dedurne un taglio di almeno $8$ archi. Con quale probabilità un'assegnazione casuale taglia almeno $8$ archi?
2. Derandomizzare: nell'ordine $0,1,\dots,9$ piazzare ogni vertice dalla parte che taglia più archi verso i vicini già piazzati (a parità, parte $0$). Riportare le attese condizionali dopo ogni passo e il taglio finale.
3. Il taglio massimo vale $12$. Quanti dei $2^{10}$ assegnamenti lo raggiungono?
4. Mostrare con $K_n$ che il fattore $\frac12$ del teorema non si può migliorare in generale.

Soluzione

1. Valore atteso. Per ogni arco $\{u,v\}$ la probabilità che $u$ e $v$ cadano da parti opposte è $\frac12$. Per la linearità $E[\text{taglio}]=\frac{15}2=7{,}5$ e, essendo il taglio un intero, esiste un'assegnazione con taglio $\ge\lceil7{,}5\rceil=\boxed8$. La distribuzione esatta sui $1024$ assegnamenti (confronto con il metodo) è

con media $7{,}5$. La probabilità di un taglio $\ge8$ è $\frac{150+120+120+60+10}{1024}=\frac{460}{1024}=\boxed{0{,}449}$.

2. Derandomizzazione. L'attesa condizionale con i primi $i$ vertici piazzati è $$E[\text{taglio}\mid\cdot]=(\text{archi con entrambi gli estremi piazzati e tagliati})+\tfrac12(\text{archi non ancora decisi}).$$ Ogni passo sceglie la parte che massimizza gli archi tagliati verso i vicini già piazzati; con $c_0$ (archi tagliati se il vertice va in $0$) e $c_1$ (se va in $1$) l'attesa cresce di $\max(c_0,c_1)-\frac{c_0+c_1}2\ge0$.

Qui $c_0$ conta i vicini già piazzati nella parte $1$ e $c_1$ quelli nella parte $0$. Per esempio al vertice $8$ i vicini piazzati sono $3$ (parte $1$), $6$ (parte $0$), $5$ (parte $1$): in parte $0$ si tagliano $3$ e $5$, cioè $c_0=2$; in parte $1$ solo $6$, cioè $c_1=1$; si sceglie la parte $0$ con guadagno $2-\frac32=\frac12$. Parti finali: $0,2,4,6,7,8\to$ parte $0$; $1,3,5,9\to$ parte $1$. Taglio finale: $\boxed{12}$, cioè il massimo: l'attesa non è mai scesa e il taglio è $\ge7{,}5$ con grande margine.

3. Quanti raggiungono il massimo. Dalla tabella: $10$ assegnamenti su $1024$ (cioè $5$ tagli distinti, ognuno contato con il suo complementare). Un'assegnazione casuale raggiunge $12$ con probabilità $\frac{10}{1024}=0{,}0098$: l'algoritmo deterministico trova in un passaggio quello che a caso richiederebbe in media circa $100$ tentativi.

4. Il fattore $\frac12$ è ottimo in generale. In $K_n$ ci sono $\binom n2$ archi e il taglio massimo ha una parte da $\lfloor n/2\rfloor$ vertici: $\lfloor n^2/4\rfloor$ archi. Rapporto taglio massimo / numero di archi: $K_4$: $\frac46=0{,}667$; $K_5$: $\frac6{10}=0{,}6$; $K_{10}$: $\frac{25}{45}=0{,}556$; $K_{100}$: $\frac{2500}{4950}=0{,}505$. Il rapporto tende a $\frac12$: non esiste una costante $c>\frac12$ tale che ogni grafo abbia un taglio di almeno $c\,|E|$ archi.

Codice di verifica

from collections import Counter

arc = [(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)] \
    + [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
taglio = lambda side: sum(side[u] != side[v] for u, v in arc)

dist = Counter(taglio([(m >> v) & 1 for v in range(10)]) for m in range(1 << 10))
print(sorted(dist.items()), sum(k * c for k, c in dist.items()) / 1024)

side = {}
for v in range(10):                                   # derandomizzazione nell'ordine 0..9
    vic = [u for a, b in arc for u in ((b,) if a == v else (a,) if b == v else ()) if u in side]
    c0 = sum(side[u] == 1 for u in vic)               # tagliati se v va in 0
    c1 = sum(side[u] == 0 for u in vic)
    side[v] = 0 if c0 >= c1 else 1
print(side, taglio(side))
for n in (4, 5, 10, 100):
    print(n, (n * n // 4) / (n * (n - 1) // 2))

Risultato: la distribuzione della tabella con media 7.5, poi {0: 0, 1: 1, 2: 0, 3: 1, 4: 0, 5: 1, 6: 0, 7: 0, 8: 0, 9: 1} 12 e i rapporti 0.667, 0.6, 0.556, 0.505.