Kargerov algoritam

Graf sa dva presecanja. Tačkasta crvena linija seče tri grane grafa. Zelena isprekidana linija predstavlja minimalni rez grafa, presecajući samo dve grane.

U informatici i teoriji grafova, Kargerov algoritam je algoritam nasumične metode koji određuje minimalan rez povezanog grafa. Izmislio ga je Dejvid Karger i prvi put objavio 1993.

Ideja algoritma je bazirana na konceptu skraćivanja grana $(u,v)$ u neorijentisanom grafu $G=(V,E)$. Neformalno govoreći, , skraćivanje broja grana spaja čvorove $u$ i $v$ u jedan, smanjujući ukupan broj čvorova u grafu za jedan. Sve ostale grane koje spajaju $u$ ili $v$ su "ponovo nakačene" za spojeni čvor, efektivno stvarajući multigraf. Kargerov osnovni algoritam iterativno skraćuje nasumično odabrane grane sve dok ne ostanu samo dva čvora; ti čvorovi predstavljaju rez u originalnom grafu. Ponavljajući ovaj osnovni algoritam dovoljan broj puta nalazimo, uz veliku verovatnoću, minimalni rez.

Globalni problem minimalnog reza

Rez $(S,T)$ u neorijentisanom grafu $G=(V,E)$ particioniše čvor $V$ u dva neprazna, razdvojena seta $S\cup T=V$. Isečak reza se sastoji od grana $\{uv\in E:u\in S,v\in T\}$ koje se nalaze između dva dela. Veličina (ili težina) reza u ne-težinskom grafu je kardinalnost isečka, npr., broj grana izmedju dva dela,

$w(S,T)=|\{uv\in E:u\in S,v\in T\}|.$

Postoji $2^{|V|}$ načina da se izabere za svaku najvišu tačku, bilo da pripada $S$ ili $T$, ali dva od ovih izbora čine $S$ ili $T$ praznim, i samim tim ne povećavaju broj rezova. Među preostalim izborima, zamenjivanjem uloga $S$ i $T$ se ne menja rez, tako da se svaki rez broji dva puta; stoga, postoji $2^{|V|-1}-1$ različitih rezova. Problem minimalnog reza je da nađe rez najmanje veličine od ovih rezova.

Za težinske grafove sa granama pozitivne težine $w:E\to {𝐑}^{+}$ težina reza predstavlja sumu težine grana izmedju čvorova u svakom delu

$w(S,T)=\sum _{uv\in E:u\in S,v\in T}w(uv),$

što se i slaže sa ne-težinskom definicijom za $w=1$.

Rez se ponekad naziva i “globalni rez” kako bi se razlikovao od “$s$-$t$ reza” za dati par temena, koji ima i dodatni zahtev(uslov) da $s\in S$ i $t\in T$. Svaki globalni rez je $s$-$t$ rez za neke $s,t\in V$. Prema tome, problem minimalnog reza moze biti rešen u polinomijalnom vremenu tako što ćemo da iterišemo(označimo) sve slučajeve $s,t\in V$ i rešavajući rezultujući minimum $s$-$t$ problema reza koristeći teoremu o maksimalnom protoku-minimalnom rezu i algoritam polinomijalnog vremena za maksimalni protok, kao što je Ford-Fulkersonov algoritam, iako ovaj pristup nije preporučljiv (optimalan). Postoji deterministički algoritam za globalni problem minimalnog reza koji se izvršava u vremenu $O(mn+n^2\log n)$.

Algoritam skraćivanja

Fundamentalna operacija Kargerovog algoritma je forma skraćivanja broja grana. Rezultat skraćivanja grane $e=\{u,v\}$ je novi čvor $uv$. Svaka grana $\{w,u\}$ ili $\{w,v\}$ za $w\notin \{u,v\}$ do krajnjih tačaka skraćene grane je zamenjena granom $\{w,uv\}$ do novog čvora. Konačno, skraćeni čvorovi $u$ i $v$ sa svim svojim starim granama su uklonjeni. Rezultujući graf ne sadrži petlje. Rezultat skraćene grane $e$ se označava kao $G/e$.

Algoritam skraćivanja iznova i iznova smanjuje nasumično izabrane grane grafa sve dok ne ostanu samo dva čvora, a u tom trenutku postoji samo jedan rez.

Uspešan prolazak kroz graf sa 10 čvorova koristeći Kargerovog algoritam. Minimalan broj rezova je 3.

   procedura skraćivanje($G=(V,E)$):
   dok $|V|>2$
       izaberi $e\in E$ nasumično ravnomerno
       $G\leftarrow G/e$
   vrati jedini rez iz $G$ 

Kada je graf predstavljen listom susedstva ili matricom povezanosti, operacija skraćivanja jedne grane može biti implementirana linearnim brojem ažuriranja glavne strukture, uz ukupno vreme izvršavanja $O(|V{|}^2)$. Alternativno, procedura može biti pregledana uz pomoć Kruskalovog algoritma za konsturisanje minimalnog razapinjućeg stabla gde su grane težine $w(e_i)=\pi (i)$ na osnovu nasumične permutacije $\pi$. Uklanjanjem najteže grane ovog stabla se dobijaju dve komponente koje opisuju rez. Na ovaj način, procedura skraćivanja može biti implementirana uz pomoć Kruskalovog algoritma u vremenu $O(|E|\log |E|)$.

Izbori nasumičnih grana uz pomoć Kargerovog algoritmu korespondira sa izvršavanjem Kruskalovog algoritma u grafu sa granama nasumičnog ranga sve dok ne ostanu samo dve komponente.

Najbolja poznata implementacija je $O(|E|)$ vremenske i prostorne složenosti, ili u $O(|E|\log |E|)$ vremenu i $O(|V|)$ prostoru.

Verovatnoća uspešnosti algoritma za skraćivanje

U grafu $G=(V,E)$ sa $n=|V|$ čvorova, algoritam skraćivanja vraća minimalan rez sa polinomijalno malom verovatnoćom ${(\genfrac{}{}{0ex}{}{n}{2})}^{-1}$. Svaki graf ima $2^{n-1}-1$ rezova, među kojima najviše može biti $(\genfrac{}{}{0ex}{}{n}{2})$ minimalnih rezova. Stoga, verovatnoća uspešnosti ovog algoritma je mnogo bolja od verovatnoće odabiranja reza nasumično, što je najviše $(\genfrac{}{}{0ex}{}{n}{2})/(2^{n-1}-1)$

Na primer, ciklični graf sa $n$ čvorova ima tačno $(\genfrac{}{}{0ex}{}{n}{2})$ minimalnih rezova, gledavši na svaki izbor od po 2 grane. Procedura skraćivanja nalazi svaku od navedenih sa jednakom verovatnoćom.

Kako bi generalno postavili verovatnoću uspešnosti, neka $C$ bude oznaka za ivice odredjenog minimalnog reza veličine $k$. Algoritam skraćivanja vraća $C$ ako nijedna od nasumičnih grana ne pripada isečku od $C$. U stvari, skraćivanje prve ivice izbegava $C$, a to se događa sa verovatnoćom $1-k/|E|$. Minimalni stepen $G$ je najmanje $k$ (u suprotnom najviša tačka najmanjeg stepena bi indicirala manji rez), tako da je $|E|\ge nk/2$. Stoga, verovatnoća da algoritam skraćivanja izabere granu iz $C$ je

$\frac{k}{|E|}\le \frac{k}{nk/2}=\frac{2}{n}.$

Verovatnoća $p_n$ da algoritam skraćivanja na $n$-čvorni graf izbegne $C$ zadovoljava rekurentnu jednačinu $p_n\ge (1-\frac{2}{n})p_{n-1}$, sa $p_2=1$, što se može proširiti

$p_n\ge \prod _{i=0}^{n-3}(1-\frac{2}{n-i})=\prod _{i=0}^{n-3}\frac{n-i-2}{n-i}=\frac{n-2}{n}\cdot \frac{n-3}{n-1}\cdot \frac{n-4}{n-2}\cdots \frac{3}{5}\cdot \frac{2}{4}\cdot \frac{1}{3}={(\genfrac{}{}{0ex}{}{n}{2})}^{-1}.$

Ponavljanje algoritma skraćivanja

10 ponavljanja procedure skraćivanja. Peto ponavljanje nalazi minilani rez veličine 3.

Ponavljanjem algoritma skraćivanja $T=(\genfrac{}{}{0ex}{}{n}{2})\ln n$ puta sa nezavisnim nasumičnim izborima i vraćanjem najmanjeg reza, verovatnoća da se ne nađe minimalan rez je

$[1-{(\genfrac{}{}{0ex}{}{n}{2})}^{-1}{]}^T\le \frac{1}{e^{\ln n}}=\frac{1}{n}.$

Ukupno vreme odradjivanja za $T$ ponavljanja za graf sa $n$ čvorova i $m$ grana je $O(Tm)=O(n^{2}m\log n)$.

Karger-Štajnov algoritam

Nastavak (produžetak) Kargerovog algoritma usled -{David Karger}- i -{Clifford Stein}- dostiže unapređenje za nivo više.

Osnovna ideja je da se izvršava procedura skraćivanja sve dok graf ne dostigne $t$ čvorova.

   procedura skraćivanje($G=(V,E)$, $t$):
   dok $|V|>t$
       izaberi$e\in E$ nasumično ravnomerno
       $G\leftarrow G/e$
   vrati $G$

Verovatnoća $p_{n,t}$ da ova procedura skraćivanja izbegne određen rez $C$ u $n$-čvornom grafu je

$p_{n,t}\ge \prod _{i=0}^{n-t-1}(1-\frac{2}{n-i})=(\genfrac{}{}{0ex}{}{t}{2})/(\genfrac{}{}{0ex}{}{n}{2}).$

Ovaj izraz je $\mathrm{\Omega }(t^2/n^2)$ i postaje manji nego od $\frac{1}{2}$ oko $t=\lceil 1+n/\sqrt{2}\rceil$. Verovatnoća da je grana iz $C$ skraćena raste kako se približava kraju. Ovo motiviše ideju prebacivanja na sporiji algoritam posle određenog broja skraćivanja (koraka skraćivanja).

   procedura brziminrez($G=(V,E)$):
   ako $|V|<6$:
       vrati minrez($V$)
   u suprotnom:
       $t\leftarrow \lceil 1+|V|/\sqrt{2}\rceil$
       $G_1\leftarrow$ skrati($G$, $t$)
       $G_2\leftarrow$ skrati($G$, $t$)
       vrati min {brziminrez($G_1$), brziminrez($G_2$)}

Analiza

Verovatnoća $P(n)$ da će algoritam pronaći određeni isečak $C$ je zadata rekurentnom relacijom

$P(n)=1-{(1-\frac{1}{2}P(\lceil 1+\frac{n}{\sqrt{2}}\rceil ))}^2$

sa rešenjem $P(n)=O\left(\frac{1}{\log n}\right)$. Vreme trajanje(izvršavanja) funckije brziminrez zadovoljava

$T(n)=2T(\lceil 1+\frac{n}{\sqrt{2}}\rceil )+O(n^2)$

sa rešenjem $T(n)=O(n^2\log n)$. Kako bi se dostigla verovatnoća greške $O(1/n)$, algoritam može biti ponavljan $O(\log n/P(n))$ puta, za sveukupno vreme $T(n)\cdot \frac{\log n}{P(n)}=O(n^2{\log }^{3}n)$. Ovo je unapredjenje u odnosu na Kargerov originalni algoritam.

Pronalaženje svih minimalnih rezova

Teorema: Sa velikom verovatnoćom možemo naći sve minimalne rezove u vremenu $O(n^2{\ln }^{3}n)$.

Dokaz: Pošto znamo da je $P(n)=O\left(\frac{1}{\ln n}\right)$, stoga nakon izvršavanja ovog algoritma$O({\ln }^{2}n)$ puta, verovatnoća da se minimalni rez ne pronađe je

$\mathrm{Pr}[\text{neuspelo nalaženje odredjenog min-reza}]=(1-P(n){)}^{O({\ln }^{2}n)}\le {(1-\frac{c}{\ln n})}^{\frac{3{\ln }^{2}n}{c}}\le e^{-3\ln n}=\frac{1}{n^3}$.

Postoji najmanje $(\genfrac{}{}{0ex}{}{n}{2})$ minimalnih rezova, otuda je verovatnoća za ne-nalaženje bilo kog minimalnog reza

$\mathrm{Pr}[\text{neuspelo nalaženje bilo kog min-reza}]\le (\genfrac{}{}{0ex}{}{n}{2})\cdot \frac{1}{n^3}=O\left(\frac{1}{n}\right).$

Verovatnoća za neuspeh u pronalaženju je izuzetno mala kada je n dovoljno veliko.∎

Poboljšanje

Kako bi se odredio minimalni rez mora se proći kroz sve grane grafa bar jednom, što se obavlja za u $O(n^2)$ vremenu u gustom grafu. Karger-Štajnov algoritam za određivanje minimalnog reza se izvršava u $O(n^2{\ln }^{O(1)}n)$ vremenu, što je približno gore navedenom.