Goldberg-Tarjan-Algorithmus

Der Goldberg-Tarjan-Algorithmus, auch Push-Relabel-Algorithmus genannt, ist ein Algorithmus aus der Graphentheorie zur Berechnung eines maximalen s-t-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: 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 δ ⁺ (v) die Menge der Kanten, die den Knoten v verlassen.

Der Algorithmus berechnet einen maximalen s-t-Fluss, indem er einen 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: V(G) \rightarrow \mathbb{N}_0$ mit ψ(s) = | V(G) | , ψ(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 ψ(v) = ψ(w) + 1 erfüllt.

Der Algorithmus arbeitet wie folgt:

1. Setze für alle Kanten $e\in \delta^+(s)$: f(e): = u(e), und für alle anderen Kanten e: f(e): = 0.
2. Setze ψ(s): = | V(G) | und für alle anderen Knoten v: ψ(v): = 0.
3. 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 tue:

   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 ψ „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 ψ 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 ψ 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 ψ(v) = i geführt wird (also für jeden Wert, den ψ theoretisch annehmen kann), zusätzlich muss das jeweils aktuelle Maximum von ψ auf der Menge der aktiven Knoten nachgehalten werden. Dies ist erforderlich, damit in jedem Durchlauf der Schleife ein aktiver Knoten v mit maximalen ψ(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