Goldberg-Tarjan algorithm

The Goldberg-Tarjan algorithm , also known as the push-relabel algorithm , is an algorithm from graph theory for calculating a maximum flow in a network . It was developed by Andrew Goldberg and Robert Endre Tarjan and published in 1988.

The algorithm

In the following, the directional graph in the network , the capacity function ( indicating the capacity of an edge ), the node from which the flow starts, and the destination node of the flow. denotes the set of nodes of the graph , the set of edges and the set of edges that leave the node . ${\displaystyle (G,u,s,t)}$ ${\displaystyle G}$ ${\displaystyle u\colon E(G)\rightarrow \mathbb {R} _{+}}$ ${\displaystyle u(e)}$ ${\displaystyle e}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle V(G)}$ ${\displaystyle G}$ ${\displaystyle E(G)}$ ${\displaystyle \delta ^{+}(v)}$ ${\displaystyle v}$

The algorithm calculates a maximum st-flow by modifying a flow until it is an st-flow. If this occurs, the obtained st-flow is also maximal. The algorithm also works with a distance marker, i. H. with a function with , and for all edges . An edge of the residual graph is called allowed if it satisfies. ${\displaystyle f}$ ${\displaystyle \psi \colon V(G)\rightarrow \mathbb {N} _{0}}$ ${\displaystyle \psi (s)=|V(G)|}$ ${\displaystyle \psi (t)=0}$ ${\displaystyle e=(v,w)\in G_{f}:\ \psi (v)\leq \psi (w)+1}$ ${\displaystyle (v,w)\in E(G_{f})}$ ${\displaystyle G_{f}}$ ${\displaystyle \psi (v)=\psi (w)+1}$

The algorithm works as follows:

1. Set for all edges : and for all other edges : . ${\displaystyle e\in \delta ^{+}(s)}$ ${\displaystyle f(e):=u(e)}$ ${\displaystyle e}$ ${\displaystyle f(e):=0}$
2. Set and for all other nodes : . ${\displaystyle \psi (s):=|V(G)|}$ ${\displaystyle v}$ ${\displaystyle \psi (v):=0}$
3. As long as there is an active node (i.e. a node with more flow arriving than flowing away), choose such a node and do: ${\displaystyle v\in V(G)}$ ${\displaystyle v\in V(G)\setminus \{s,t\}}$ ${\displaystyle v}$

   If no allowed edge leaves the node in the residual graph , set ${\displaystyle G_{f}}$ ${\displaystyle v}$ ${\displaystyle \psi (v):=\min\{\psi (w)+1\mid \exists e\in E(G_{f}):e=(v,w)\}}$

   Otherwise augment along an allowed edge that leaves (i.e. if is, set ; otherwise is , and thus the rear edge of an edge , then set . Here, the residual capacities and the excess at the node denote the difference between the incoming and outgoing flow. ). ${\displaystyle f}$ ${\displaystyle e}$ ${\displaystyle v}$ ${\displaystyle e\in E(G)}$ ${\displaystyle f(e):=f(e)+\min\{u_{f}(e),\operatorname {ex} (v)\}}$ ${\displaystyle e\in E(G_{f})\setminus E(G)}$ ${\displaystyle e={\overleftarrow {g}}}$ ${\displaystyle g\in E(G)}$ ${\displaystyle f(g):=f(g)-\min\{u_{f}(e),\operatorname {ex} (v)\}}$ ${\displaystyle u_{f}}$ ${\displaystyle \operatorname {ex} (v)}$ ${\displaystyle v}$ ${\displaystyle v}$

A modification of the flow in step 3 is also called “push”, a modification of the distance marking “relabel”. Hence the name Push Relabel Algorithm. ${\displaystyle f}$ ${\displaystyle \psi }$

At the end there is a maximum st flow. Because at any point in time the node is the only source and the algorithm does not stop until the node is the only sink. Since a distance marking always remains and thus fulfills the properties described above, it is ensured that the node in the residual graph can never be reached from the source . This ensures that the st-flow calculated by the algorithm is actually a maximum st-flow. ${\displaystyle f}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle \psi }$ ${\displaystyle G_{f}}$ ${\displaystyle t}$ ${\displaystyle s}$

running time

As general as stated above, the algorithm has a running time of . ${\displaystyle {\mathcal {O}}(|V(G)|^{2}\ |E(G)|)}$

If you always select an active node in step 3 of the algorithm , for which the distance marker has the maximum value among all active nodes (i.e. one with ), a running time of can be proven. In the implementation, however, this requires that for each value of up each a list of all active nodes to run (ie for each value that can take in theory), must also the respective current maximum of be tracked on the set of active nodes. This is necessary so that an active node with a maximum without loss of runtime can be selected in each run of the loop . ${\displaystyle v}$ ${\displaystyle \psi }$ ${\displaystyle v}$ ${\displaystyle \psi (v)=\max\{\psi (x)\mid x{\text{ ist aktiver Knoten}}\}}$ ${\displaystyle {\mathcal {O}}(|V(G)|^{2}{\sqrt {|E(G)|}})}$ ${\displaystyle i}$ ${\displaystyle 0}$ ${\displaystyle 2{\mathopen {|}}V(G){\mathclose {|}}-2}$ ${\displaystyle v}$ ${\displaystyle \psi (v)=i}$ ${\displaystyle \psi }$ ${\displaystyle \psi }$ ${\displaystyle v}$ ${\displaystyle \psi (v)}$

With more sophisticated implementations, runtimes of

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

and

${\displaystyle {\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 }))}$

to reach. Here denotes the maximum value of the capacity function . ${\displaystyle u_{\max }}$ ${\displaystyle u}$

swell

• Dieter Jungnickel : Graphs, Networks and Algorithms , Springer (1998) ISBN 978-3-540-72779-8
• Bernhard Korte , Jens Vygen : Combinatorial Optimization: Theory and Algorithms . Translated from the English by 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

Individual evidence

1. ^ Andrew Goldberg, Robert Tarjan: A new approach to the maximum flow problem . In: Journal of the ACM . tape 35 , 1988, pp. 921-940 .
2. ^ Bernhard Korten, Jens Vygen: Combinatorial Optimization . 3. Edition. 2006, p. 168 .