V předchozí sekci jsme si vysvětlili Golgbergův push-relabel algoritmus. Teď je naším cílem určit jeho časovou složitost. Chceme dokázat následující věty.

Věta 1: Algoritmus push-relabel provede $\OO(n^2)$ zvýšení vrcholů a $\OO(mn^2)$ protlačení po hraně.
Věta 2: Algoritmus maximum distance push-relabel provede $\OO(n^2)$ zvýšení vrcholů a $\OO(n^3)$ protlačení po hraně.

První větu dokážeme řadou lemmat. Lemmata platí pro obecný push-relabel algoritmus. Akorát lemma 7 „o počtu nenasycujících protlačení 2“ platí pouze pro maximum distance pust-relabel algoritmus. Jeho přidáním k předchozím lemmatům dokážeme druhou větu.

Lemma 3 (o cestě do zdroje): Je-li $f$ je pratok a $w$ je aktivní vrchol, potom v $G_f$ existuje orientovaná cesta z $w$ do zdroje $s$.
Důkaz: Sporem, nechť z $w$ nevede orientovaná cesta do $s$. Označme jako $R$ množinu vrcholů, ze kterých v $G_f$ vede orientovaná cesta do zdroje $s$. Potom v $G_f$ nevede žádná hrana z $\overline{R}$ do $R$ a proto $f(\delta(R))=0$. Sečtěme nerovnosti $f(v)\geq 0$ pro všechny $v\in\overline{R}$ a dostaneme $X:= \sum_{v\in\overline{R}} f(v) \geq 0$. Na druhou stranu, když sečteme příspěvky přebytků po hranách, tak dostaneme $X= f(\delta(R))-f(\delta(\overline{R}))$ (každá hrana $uv$ s oběma konci v $\overline{R}$ přispěje do $f(v)$ kladně a do $f(u)$ záporně a proto je její příspěvek do $X$ roven nule). Protože $f(\delta(R))=0$, tak z nerovnosti $ f(\delta(R))-f(\delta(\overline{R})) \geq 0$ dostáváme $f(\delta(\overline{R}))=0$. Součet nerovností platí s rovností a proto i každá nerovnost platí s rovností. To je spor s tím, že pro $w\in \overline{R}$ je $f(w)\gt 0$.

Lemma 4 (o maximálním počtu zvýšení): V každém kroku algoritmu pro každý vrchol $v\in V$ je $d(v)\leq 2n-1$. Každý vrchol se zvýší nejvýše $2n-1$ krát a tedy celkem proběhne nejvýše $\OO(n^2)$ zvýšení.
Důkaz: Každé zvýšení proběhne alespoň o jedna. Zvyšovány jsou pouze aktivní vrcholy a z těch vždy vede cesta do zdroje (lemma 3 „o cestě do zdroje“). Tedy $d_f(v,s)\leq n-1$. Z lemmatu 2 „dolní odhad vzdálenosti 2 vrcholů“ víme, že $d_f(v,s) \geq d(v) – n$. Kombinací obou nerovností dostaneme $d(v)\leq 2n-1$.

Operace protlačení rozdělíme na dva typy podle toho, jestli se při ní hrana nasytila a nebo ne. Protlačení po hraně $vw$ je nasycující, pokud byl přebytek ve $v$ větší než rezerva hrany $vw$. Po nasycujícím protlačení zmizí hrana $vw$ z $G_f$. V opačném případě je protlačení po hraně $vw$ nenasycující a v tomto případě přestal být vrchol $v$ aktivní.

Lemma 5 (o počtu nasycujících protlačení): Počet nasycujících protlačení během algoritmu je nejvýše $2mn$.
Důkaz: Podívejme se na pevný pár $(v, w)$ takový, že $vw\in E$ nebo $wv\in E$. Po nasycujícím protlačení po hraně $vw$ hrana $vw$ zmizí z $G_f$. Proto mezi dvěma nasycujícími protlačeními po hraně $vw$ musí proběhnout protlačení po opačné hraně $wv$, aby se hrana $vw$ opět objevila v $G_f$.







Protlačování probíhá pouze po přípustných hranách, vedoucích z kopce o jedna dolů. Hodnota $d(v)$ nikdy neklesá a proto musí být mezi dvěma nasycujícími protlačeními po $vw$ alespoň jedna operace zvýšení vrcholu $v$. Zvýšení $d(v)$ bude alespoň o $2$ a proto podle lemmatu 4 „o maximálním počtu zvýšení“ může proběhnout nejvýše $n-1$ krát. Celkem po hraně $vw$ může proběhnout nejvýše $n$ nasycujících protlačení.

Podobně po opačné hraně $wv$ může proběhnout také nejvýše $n$ nasycujících protlačení. Celkem tedy pro všechny hrany v původní síťi $G$ proběhne nejvýše $2mn$ nasycujících protlačení.

Lemma 6 (o počtu nenasycujících protlačení): Počet nenasycujících protlačení během algoritmu je nejvýše $\OO(mn^2)$.
Důkaz: Nechť $A$ je množina aktivních vrcholů vzhledem k pratoku $f$ a $D=\sum_{v\in A} d(v)$. Na začátku algoritmu je $D=0$ a nikdy není záporné.

  • Každé zvýšení vrcholu zvětšuje $D$.
  • Nasycující protlačení po hraně $vw$ může zvětšit $D$ až o $2n-1$, protože $v$ může zůstat aktivní a vrchol $w$ se může stát aktivním. Podle lemma [ref]lemma_zvysovani[/ref] je $d(w)\leq 2n-1$.
  • Nenasycující protlačení po $vw$ zmenší $D$. Vrchol $v$ přestane být aktivní. Proto se $D$ zmenší buď o $d(v)$ nebo o $d(v)-d(w)=1$, pokud se zároveň $w$ stane aktivním.

Všechny zvětšení $D$ během algoritmu jsou kvůli zvýšení vrcholů a nebo kvůli nasycujícím protlačením. Podle lemma 4 „o maximálním počtu zvýšení“ a lemma 5 „o počtu nasycujících protlačení“ během celého algoritmu vzroste hodnota $D$ o nejvýše $(n-2)(2n-1)+2mn(2n-1)=\OO(mn^2)$. Každý nenasycující protlačení sníží tuto hodnotu alespoň o jedna a proto proběhne nejvýše $\OO(mn^2)$ nenasycujících protlačení.

Lemma 7 (o počtu nenasycujících protlačení 2): Počet nenasycujících protlačení během maximum distance push-relabel algoritmu je nejvýše $\OO(n^3)$.
Důkaz: Každé nenasycující protlačení po $vw$ deaktivuje vrchol $v$. Protože vždy zpracováváme vrchol $v$ s největším $d(v)$, tak je $d(w)\leq d(v)$ pro všechny aktivní vrcholy $w$. Před tím, než se $v$ stane znovu aktivním, musí proběhnout zvýšení nějakého souseda $v$ (a protlačení toku z tohoto souseda do $v$).

Z toho dostáváme, že když proběhne $n$ nenasycujících protlačení a žádné zvýšení vrcholu, tak žádný vrchol není aktivní a algoritmus skončí. Proto je počet nenasycujících protlačení nejvýše $n$ krát větší než počet zvýšení a to je nejvýše $\OO(n^3)$.

Poznamenejme, že jsou i další pravidla pro výběr aktivních vrcholů a dávají také odhad $\OO(n^3)$ na celkový počet protlačení (například FIFO push-relabel). My jsme si vybrali pravidlo maximum distance z toho důvodu, že pro něj Tuncel v roce 1994 dokázal lepší analýzu a ukázal odhad $\OO(n^2\sqrt{m})$ na počet protlačení (viz lemma „Tuncelův odhad“).