Kargerov algoritam

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.

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.

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\colon 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\colon 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\colon E\rightarrow \mathbf {R} ^{+}$ težina reza predstavlja sumu težine grana izmedju čvorova u svakom delu

$w(S,T)=\sum _{uv\in E\colon 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 ${\binom {n}{2}}^{-1}$. Svaki graf ima $2^{n-1}-1$ rezova, među kojima najviše može biti ${\tbinom {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 ${\tbinom {n}{2}}/(2^{n-1}-1)$

Na primer, ciklični graf sa $n$ čvorova ima tačno ${\binom {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|\geq nk/2$. Stoga, verovatnoća da algoritam skraćivanja izabere granu iz $C$ je

${\frac {k}{|E|}}\leq {\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}\geq {\bigl (}1-{\frac {2}{n}}{\bigr )}p_{n-1}$, sa $p_{2}=1$, što se može proširiti

$p_{n}\geq \prod _{i=0}^{n-3}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}=\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}}={\binom {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={\binom {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

${\Bigl [}1-{\binom {n}{2}}^{-1}{\Bigr ]}^{T}\leq {\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}\geq \prod _{i=0}^{n-t-1}{\Bigl (}1-{\frac {2}{n-i}}{\Bigr )}={\binom {t}{2}}{\Bigg /}{\binom {n}{2}}\,.$

Ovaj izraz je $\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-\left(1-{\frac {1}{2}}P\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)\right)^{2}$

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

$T(n)=2T\left({\Bigl \lceil }1+{\frac {n}{\sqrt {2}}}{\Bigr \rceil }\right)+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

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

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

$\Pr[{\text{neuspelo nalaženje bilo kog min-reza}}]\leq {\binom {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.