Hopkroft-Karp algoritam

U računarstvu, Hopcroft-Karp algoritam je algoritam koji kao ulaz ima bipartitni graf, a kao izlaz daje uparivanje sa maksimalnim brojem grana, najveći skup grana koje nemaju zajedničke krajnje tačke. Vremenska složenost algoritma je $O(|E|{\sqrt {|V|}})$ u najgorem slučaju, gde je $E$ skup grana, a $V$ skup čvorova grafa. U slučaju gustih grafova složenost postaje ključna $O(|V|^{2.5})$ , a za slučajne grafove je linearna. Algoritam su razvili John Hopcroft i Richard Karp (1973 godine). Kao i prethodni algoritmi koji se odnose na uparivanje kao sto su Mađarski algoritam i rad Edmonds-a (1965), Hopcroft-Karp algoritam stalno povećava veličinu delimičnog uparivanja pronalaženjem alternirajućih puteva. Međutim, umesto da pronalazi samo jedan alternirajući put po iteraciji, algoritam pronalazi maksimalni skup najkraćih alternirajućih puteva. Kao rezultat toga samo $O({\sqrt {n}})$ iteracija je potrebno. Isti princip je korišćen pri razvijanju složenijih algoritama za ne-bipartitno uparivanje sa istom asimptotskom složenošću kao i Hopcroft-Karp algoritam.

Alternirajući putevi

Teme koje ne pripada grani koja se nalazi u skupu delimično uparenih grana $M$, se zove slobodno(neupareno) teme. Osnovni koncept na kom se algoritam zasniva je vezan za alternirajuće puteve, puteve koji počinju i završavaju se neuparenim čvorom, a naizmenično prolaze kroz grane koje su ušle u skup uparenih i kroz one koje nisu. Broj grana na tom putu mora biti neparan, jer pocinje i završava se neuparenim čvorom. Neka je $E$ skup čvorova sa njihovim granama, a $M$ skup uparenih čvorova sa njihovim granama . Alternirajući put $P$ za dato uparivanje $M$ je put između dva neuparena čvora, pri čemu su grane puta $P$ naizmenično u $E/M$, odnosno $M$. Broj grana koje pripadaju skupu $E/M$ ima za jedan više nego onih koje pripadaju skupu $M$ . Prema tome, ako iz uparivanja izbacimo sve grane koje pripadaju skupu $M$, a ubacimo sve one koje pripadaju skupu $E/M$, dobićemo uparivanje sa jednom granom više. Jasno je da ako za dato uparivanje postoji alternirajući put, onda ono nije optimalno. Ispostavlja se da je i obrnuto tvrđenje tačno. Uparivanje je optimalno ako i samo ako nema alternirajući put.

Alternirajući put u problemu uparivanja je blisko povezan sa alternirajućim putevima u problemu maksimalnog protoka. Moguće je transformisati problem bipartitnog uparivanja u primer problema maksimalnog protoka, tako sto alternirajući putevi u problemu uparivanja postanu alternirajući putevi u problemu protoka. U stvari, generalizacija tehnike koja se koristi u Hopcroft-Karp algoritmu je poznata kao Dinic algoritam.

Input: Bipartite graph $G(U\cup V,E)$

Output: Matching $M\subseteq E$

$M\leftarrow \emptyset$

repeat

${\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}$ maksimalan skup čvorova koji ne pripadaju najkraćim alternirajućim putevima

$M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})$

until ${\mathcal {P}}=\emptyset$

Algoritam

Neka $U$ i $V$ budu dva skupa u bipartitnom grafu $G$, i neka se uparivanje iz $U$ u $V$ u bilo koje vreme može predstaviti kao skup $M$. Algoritam se radi u fazama. Svaka faza se sastoji od sledećih koraka.

• BFS pretraga deli particije čvorova grafa na slojeve. Slobodni čvorovi iz $U$ se koriste kao polazna temena za pretragu, i formira se prvi sloj particije. Tokom prvog nivoa pretrage možemo proći samo kroz neuparene ivice (pošto slobodni čvorovi iz U po definiciji ne pripadaju uparenim granama), u narednim nivoima pretrage, prolazićemo naizmenično kroz uparene i neuparene grane. Prilikom traženja susednih čvorova počev od čvorova iz $U$ , možemo proći jedino kroz neuparene grane, dok iz čvorova koji pripadaju $V$ možemo proći samo kroz uparene grane. Pretraga se završava na prvom sloju $K$ gde su pronađeni jedan ili više slobodnih čvorova iz $V$.
• Svi slobodni čvorovi iz $V$ na sloju $k$ se nalaze u skupu $F$. Cvor $v$ se nalazi u $F$ ako i samo ako je kraj najkraćeg alternirajućeg puta.
• Algoritam pronalazi maksimalan skup čvorova koji ne pripadaju alternirajućim putevima dužine $k$. Ovaj skup može biti napravljen DFS pretragom iz $F$ do slobodnih čvorova iz $U$, korišćenjem BFS slojeva kao vodič, DFS pretragom možemo proći kroz grane koje vode do neposećenih čvorova na prethodnom sloju, a DFS stablo sadrži naizmenično uparene i neuparene grane. Čim je pronađen alternirajući put koji sadrži jedan od čvorova iz $F$, DFS pretraga se nastavlja iz sledećeg početnog čvora.
• Svaki od puteva koji je pronađen na ovaj način se koristi za uvećanje $M$.

Algoritam se završava kada BFS pretragom nije pronađen ni jedan alternirajući put.

Analiza

Svaka faza se sastoji od jedne BFS pretrage i jedne DFS pretrage. Dakle, vremenska složenost jedne faze je linearna. Složenost prvih ${\sqrt {|V|}}$ faza u grafu sa $|V|$ čvorova i $|E|$ grana je $O(|E|{\sqrt {|V|}})$ . Može se pokazati da svaka faza povećava dužinu najkraćeg alternirajućeg puta za najmanje jedan, faza pronalazi maksimalan skup alternirajućih puteva zadate dužine, tako da ostali alternirajući putevi moraju biti duži. Zato, kada se početnih ${\sqrt {|V|}}$ faza algoritma završi, preostali najkraći alternirajući put ima najmanje ${\sqrt {|V|}}$ grana .Međutim, simetrična razlika eventualno optimalnog uparivanja i delimičnog uparivanja $M$ tokom prvih faza formira kolekciju čvorova i grana koje su disjunktne alternirajućim putevima i naizmeničnim ciklusima. Ukoliko je svaki put u kolekciji bar dužine ${\sqrt {|V|}}$ , može biti najvise ${\sqrt {|V|}}$ puteva u kolekciji, i velicina optimalnog uparivanja se može razlikovati od velicine $M$ za najvise ${\sqrt {|V|}}$ grana. Pošto svaka faza algoritma povećava veličinu uparivanja za barem jedan, može postojati najviše ${\sqrt {|V|}}$ dodatnih faza pre nego što se algoritam završi. Pošto algoritam ima najviše $2{\sqrt {|V|}}$ faza, njegova složenost je u najgorem slučaju $O(|E|{\sqrt {|V|}})$ . U mnogim slučajevima,algoritam ima bolju vremensku složenost. Na primer, u prosečnom slučaju, za slučajne oskudne bipartitne grafove, Bast et al. Je pokazao da sa velikom verovatnoćom sva neoptimalna uparivanja imaju alternirajuće puteve logaritamske dužine. Kao posledica, za ove grafove, Hopcroft-Karp algoritam ima $O(\log |V|)$ faza, a ukupna složenost je $O(|E|\log |V|)$ .

Ne-bipartitni grafovi

Ista ideja o pronalaženju maksimalnog skupa najkraćih alternirajućih puteva se koristi i za pronalaženje maksimalnog uparivanja u ne-bipartitnim grafovima, i iz istih razloga, algoritam baziran na ovoj ideji ima $O({\sqrt {|V|}})$ faza. Međutim, za ne-bipartitne grafove je teže pronaći alternirajuće puteve u svakoj fazi. Nadovezujući se na rad nekoliko sporijih prethodnika, Micali i Vazirani (1980) su pokazali kako se može implementirati pojedinačna faza sa linearnom složenošću, što je rezultovalo algoritmom koji ima istu vremensku složenost kao Hopcroft-Karp algoritam za bipartitne grafove. Micali-Vazirani tehnika je kompleksna i njeni autori nemaju kompletan dokaz, alternativne metode za ovaj problem su kasnije opisali drugi autori.

Pseudokod

 
 1 //G = G1 ∪ G2 ∪ {NIL}
 2 //G1 i G2 su particije grafa a NIL specijalni null čvor
 3 
 4 
 5    function BFS ()
 6    for v in G1
 7        if Pair_G1[v] == NIL
 8            Dist[v] = 0
 9           Enqueue(Q,v)
 10       else
 11           Dist[v] = ∞
 12    Dist[NIL] = ∞
 13    while Empty(Q) == false
 14        v = Dequeue(Q)
 15        if Dist[v] < Dist[NIL] 
 16            for each u in Adj[v]
 17                if Dist[ Pair_G2[u] ] == ∞
 18                    Dist[ Pair_G2[u] ] = Dist[v] + 1
 19                    Enqueue(Q,Pair_G2[u])
 20    return Dist[NIL] != ∞

 1    function DFS (v)
 2    if v != NIL
 3        for each u in Adj[v]
 4            if Dist[ Pair_G2[u] ] == Dist[v] + 1
 5                if DFS(Pair_G2[u]) == true
 6                    Pair_G2[u] = v
 7                    Pair_G1[v] = u
 8                    return true
 9        Dist[v] = ∞
 10           return false
 11   return true

 1    function Hopcroft-Karp
 2        for each v in G
 3            Pair_G1[v] = NIL
 4            Pair_G2[v] = NIL
 5        matching = 0
 6        while BFS() == true
 7            for each v in G1
 8                if Pair_G1[v] == NIL
 9                    if DFS(v) == true
 10                       matching = matching + 1
 11    return matching