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.^[1]

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)$ .^[2]

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.

   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|)$ .

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

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,^[3] 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

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.^[4]

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.

Референце

^ ^а ^б Karger, Dejvid (1993). „Globalni minimalni rezovi u RNC-u i Other Posledice Jednostavnog Algoritma Za Minamalne Rezove”. Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms.
^ Stoer, Mechthild; Wagner, Frank (1997). „A simple min-cut algorithm”. Journal of the ACM. 44 (4): 585—591. S2CID 15220291. doi:10.1145/263867.263872.
^ Patrignani, Maurizio; Pizzonia, Maurizio (2001), „The complexity of the matching-cut problem”, Ур.: Brandstädt, Andreas; Le, Van Bang, Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14ÔÇô16, 2001, Proceedings, Lecture Notes in Computer Science, 2204, Berlin: Springer, стр. 284—295, MR 1905640, doi:10.1007/3-540-45477-2_26 .
^ Karger, David R.; Stein, Clifford (1996). „A new approach to the minimum cut problem”. Journal of the ACM. 43 (4): 601—640. S2CID 5385337. doi:10.1145/234533.234534.

[karger1993-1] а ^б Karger, Dejvid (1993). „Globalni minimalni rezovi u RNC-u i Other Posledice Jednostavnog Algoritma Za Minamalne Rezove”. Proc. 4th Annual ACM-SIAM Symposium on Discrete Algorithms.

[simplemincut-2] Stoer, Mechthild; Wagner, Frank (1997). „A simple min-cut algorithm”. Journal of the ACM. 44 (4): 585—591. S2CID 15220291. doi:10.1145/263867.263872.

[3] Patrignani, Maurizio; Pizzonia, Maurizio (2001), „The complexity of the matching-cut problem”, Ур.: Brandstädt, Andreas; Le, Van Bang, Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Germany, June 14ÔÇô16, 2001, Proceedings, Lecture Notes in Computer Science, 2204, Berlin: Springer, стр. 284—295, MR 1905640, doi:10.1007/3-540-45477-2_26 .

[faster-4] Karger, David R.; Stein, Clifford (1996). „A new approach to the minimum cut problem”. Journal of the ACM. 43 (4): 601—640. S2CID 5385337. doi:10.1145/234533.234534.

[1]

[2]

[3]

[4]