Goldberg-Tarjan-Algorithmus
# Goldberg-Tarjan-Algorithmus

Der Goldberg-Tarjan-Algorithmus, auch Push-Relabel-Algorithmus genannt, ist ein Algorithmus aus der Graphentheorie zur Berechnung eines maximalen Flusses in einem Netzwerk. Er wurde von Andrew Goldberg und Robert Endre Tarjan entwickelt und 1988 publiziert.

## Der Algorithmus

Im Folgenden bezeichnet im Netzwerk $(G,u,s,t)$ $G$ den gerichteten Graphen, $u\colon E(G)\rightarrow \mathbb {R} _{+}$ die Kapazitätsfunktion (wobei $u(e)$ die Kapazität einer Kante $e$ angibt), $s$ den Knoten, von dem der Fluss startet, und $t$ den Zielknoten des Flusses. $V(G)$ bezeichnet die Knotenmenge des Graphen $G$, $E(G)$ die Kantenmenge und $\delta ^{+}(v)$ die Menge der Kanten, die den Knoten $v$ verlassen.

Der Algorithmus berechnet einen maximalen s-t-Fluss, indem er einen s-t-Präfluss $f$ so lange modifiziert, bis er ein s-t-Fluss ist. Tritt dies ein, ist der erhaltene s-t-Fluss auch maximal. Der Algorithmus arbeitet des Weiteren mit einer Distanzmarkierung, d. h. mit einer Funktion $\psi \colon V(G)\rightarrow \mathbb {N} _{0}$ mit $\psi (s)=|V(G)|$, $\psi (t)=0$ und für alle Kanten $e=(v,w)\in G_{f}:\ \psi (v)\leq \psi (w)+1$. Eine Kante $(v,w)\in E(G_{f})$ des Residualgraphen $G_{f}$ heißt erlaubt, wenn sie $\psi (v)=\psi (w)+1$ erfüllt.

Der Algorithmus arbeitet wie folgt:

* Setze für alle Kanten $e\in \delta ^{+}(s)$: $f(e):=u(e)$, und für alle anderen Kanten $e$: $f(e):=0$.
* Setze $\psi (s):=|V(G)|$ und für alle anderen Knoten $v$: $\psi (v):=0$.
* Solange es einen aktiven Knoten $v\in V(G)$ gibt (d. h. einen Knoten $v\in V(G)\setminus \{s,t\}$, auf dem mehr Fluss ankommt als abfließt), wähle so einen Knoten $v$ und führe aus:

    Wenn im Residualgraphen $G_{f}$ keine erlaubte Kante den Knoten $v$ verlässt, setze $\psi (v):=\min\{\psi (w)+1\mid \exists e\in E(G_{f}):e=(v,w)\}$
    Ansonsten augmentiere $f$ entlang einer erlaubten Kante $e$, die $v$ verlässt (d. h.: Falls $e\in E(G)$ ist, setze $f(e):=f(e)+\min\{u_{f}(e),\operatorname {ex} (v)\}$; andernfalls ist $e\in E(G_{f})\setminus E(G)$, und somit $e={\overleftarrow {g}}$ Rückkante einer Kante $g\in E(G)$, dann setze $f(g):=f(g)-\min\{u_{f}(e),\operatorname {ex} (v)\}$. Hierbei bezeichnen $u_{f}$ die Residualkapazitäten und $\operatorname {ex} (v)$ den Überschuss am Knoten $v$, also die Differenz des an $v$ ankommenden und des abfließenden Flusses.).

Eine Modifikation des Flusses $f$ in Schritt 3 wird auch „Push“ genannt, eine Modifikation der Distanzmarkierung $\psi$ „Relabel“. Daher rührt der Name Push-Relabel-Algorithmus.

Am Ende ist $f$ ein maximaler s-t-Fluss. Denn zu jedem Zeitpunkt ist der Knoten $s$ die einzige Quelle und der Algorithmus hält erst an, wenn der Knoten $t$ die einzige Senke ist. Da $\psi$ stets eine Distanzmarkierung bleibt und damit die oben beschriebenen Eigenschaften erfüllt, ist gewährleistet, dass im Residualgraphen $G_{f}$ der Knoten $t$ niemals von der Quelle $s$ aus erreichbar ist. Damit ist sichergestellt, dass der vom Algorithmus berechnete s-t-Fluss tatsächlich ein maximaler s-t-Fluss ist.

## Laufzeit

So allgemein wie oben angegeben hat der Algorithmus eine Laufzeit von ${\mathcal {O}}(|V(G)|^{2}\ |E(G)|)$.

Wählt man in Schritt 3 des Algorithmus immer einen aktiven Knoten $v$, für den unter allen aktiven Knoten die Distanzmarkierung $\psi$ maximalen Wert hat (also ein $v$ mit $\psi (v)=\max\{\psi (x)\mid x{\text{ ist aktiver Knoten}}\}$), lässt sich eine Laufzeit von ${\mathcal {O}}(|V(G)|^{2}{\sqrt {|E(G)|}})$ beweisen. Bei der Implementierung erfordert dies jedoch, dass für jeden Wert $i$ von $0$ bis $2{\mathopen {|}}V(G){\mathclose {|}}-2$ jeweils eine Liste aller aktiven Knoten $v$ mit $\psi (v)=i$ geführt wird (also für jeden Wert, den $\psi$ theoretisch annehmen kann), zusätzlich muss das jeweils aktuelle Maximum von $\psi$ auf der Menge der aktiven Knoten nachgehalten werden. Dies ist erforderlich, damit in jedem Durchlauf der Schleife ein aktiver Knoten $v$ mit maximalen $\psi (v)$ ohne Laufzeitverlust gewählt werden kann.

Mit ausgeklügelteren Implementierungen lassen sich auch Laufzeiten von

    ${\mathcal {O}}(|V(G)|\ |E(G)|\ \log _{2+{\frac {|E(G)|}{|V(G)|\log(|V(G)|)}}}(|V(G)|))$

und

    ${\mathcal {O}}(\min\{{\sqrt {|E(G)|}},{\sqrt[{3}]{|V(G)|^{2}}}\}\ |E(G)|\ \log \left({\frac {|V(G)|^{2}}{|E(G)|}}\right)\ \log(u_{\max }))$

erreichen. Hierbei bezeichnet $u_{\max }$ den maximalen Wert der Kapazitätsfunktion $u$.

## Quellen

* Dieter Jungnickel: Graphs, Networks and Algorithms, Springer (1998) ISBN 978-3-540-72779-8
* Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. Aus dem Englischen von Rabe von Randow. Springer-Verlag, Berlin Heidelberg 2008, ISBN 978-3-540-76918-7
* Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Springer-Verlag, 2003, ISBN 3-540-44389-4
