The push-relabel algorithm is one of the most efficient algorithms to compute a maximum flow

Maximum flow problem

In optimization theory, the maximum flow problem is to find a feasible flow through a single-source, single-sink flow network that is maximum....

. The general algorithm has time complexity, while the implementation with FIFO vertex selection rule has running time, the highest active vertex selection rule provides complexity, and the implementation with Sleator's and Tarjan's dynamic tree data structure runs in time. Asymptotically, it is more efficient than the Edmonds-Karp algorithm

Edmonds-Karp algorithm

In computer science and graph theory, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O time. It is asymptotically slower than the relabel-to-front algorithm, which runs in O time, but it is often faster in...

, which runs in time.

Algorithm

Given a flow network with capacity from node u to node v given as , source s and sink t, we want to find the maximum amount of flow you can send from s to t through the network. Two types of operations are performed on nodes, push and relabel. Throughout we maintain:

• . Flow from u to v. Available capacity is .
• . We only push from u to v if . For all u, is a non-negative integer.
• . Sum of flow to and from u.

After each step of the algorithm, the flow is a preflow, satisfying:

• . The flow between and , does not exceed the capacity.
• . We maintain the net flow.
• for all nodes . Only the source may produce flow.

Notice that the last condition for a preflow is relaxed from the corresponding condition for a legal flow in a regular flow network.

We observe that the longest possible path from s to t is nodes long. Therefore it must be possible to assign height to the nodes such that for any legal flow, and , and if there is a positive flow from u to v, . As we adjust the height of the nodes, the flow goes through the network as water through a landscape. Differing from algorithms such as Ford-Fulkerson

Ford-Fulkerson algorithm

The Ford–Fulkerson Method computes the maximum flow in a flow network. It was published in 1956...

, the flow through the network is not necessarily a legal flow throughout the execution of the algorithm.

In short words, the heights of nodes (except s and t) is adjusted, and flow is sent between nodes, until all possible flow has reached t. Then we continue increasing the height of internal nodes until all the flow that went into the network, but did not reach t, has flowed back into s. A node can reach the height before this is complete, as the longest possible path back to s excluding t is long, and . The height of t is kept at 0.

Push

A push from u to v means sending a part of the excess flow into u on to v. Three conditions must be met for a push to take place:

• . More flow into the node than out of it so far.
• . Available capacity from u to v.
• . Can only send to lower node.

We send an amount of flow equal to .

Relabel

Doing a relabel on a node u is increasing its height until it is higher than at least one of the nodes it has available capacity to. Conditions for a relabel:

• . There must be a point in relabelling.
• for all v such that . The only nodes we have available capacity to are higher.

When relabelling u, we set to be the lowest value such that for some v where .

Push-relabel algorithm

Push-relabel algorithms in general have the following layout:

1. As long as there is legal push or relabel operation
   1. Perform a legal push, or
   2. a legal relabel.

The running time for these algorithms are in general (argument omitted).

Discharge

In relabel-to-front, a discharge on a node u is the following:

1. As long as :
   1. If not all neighbours have been tried since last relabel:
      1. Try to push flow to an untried neighbour.
   2. Else:
      1. Relabel u

This requires that for each node, it is known which nodes have been tried since last relabel.

Relabel-to-front algorithm, ie. using FIFO heuristic

In the relabel-to-front algorithm, the order of the push and relabel operations is given:

1. Send as much flow from s as possible.
2. Build a list of all vertices except s and t.
3. As long as we have not traversed the entire list:
   1. Discharge the current vertex.
   2. If the height of the current vertex changed:
      1. Move the current vertex to the front of the list
      2. Restart the traversal from the front of the list.

The running time for relabel-to-front is (proof omitted).

Sample implementation

Python

Python (programming language)

Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

 implementation:

def relabel_to_front(C, source, sink):
n = len(C) # C is the capacity matrix
F = ] * n for _ in xrange(n)]
# residual capacity from u to v is C[u][v] - F[u][v]

height = [0] * n # height of node
excess = [0] * n # flow into node minus flow from node
seen = [0] * n # neighbours seen since last relabel
# node "queue"
list = [i for i in xrange(n) if i != source and i != sink]

def push(u, v):
send = min(excess[u], C[u][v] - F[u][v])
F[u][v] += send
F[v][u] -= send
excess[u] -= send
excess[v] += send

def relabel(u):
# find smallest new height making a push possible,
# if such a push is possible at all
min_height = ∞
for v in xrange(n):
if C[u][v] - F[u][v] > 0:
min_height = min(min_height, height[v])
height[u] = min_height + 1

def discharge(u):
while excess[u] > 0:
if seen[u] < n: # check next neighbour
v = seen[u]
if C[u][v] - F[u][v] > 0 and height[u] > height[v]:
push(u, v)
else:
seen[u] += 1
else: # we have checked all neighbours. must relabel
relabel(u)
seen[u] = 0

height[source] = n # longest path from source to sink is less than n long
excess[source] = Inf # send as much flow as possible to neighbours of source
for v in xrange(n):
push(source, v)

p = 0
while p < len(list):
u = list[p]
old_height = height[u]
discharge(u)
if height[u] > old_height:
list.insert(0, list.pop(p)) # move to front of list
p = 0 # start from front of list
else:
p += 1

return sum(F[source])

Note that the above implementation is not very efficient. It is slower than Edmonds-Karp algorithm

Edmonds-Karp algorithm

In computer science and graph theory, the Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson method for computing the maximum flow in a flow network in O time. It is asymptotically slower than the relabel-to-front algorithm, which runs in O time, but it is often faster in...

 even for very dense graphs. To speed it up, you can do at least two things:

1. Make neighbour lists for each node, and let the index seen[u] be an iterator over this, instead of the range .
2. Use a gap heuristic. If there is a such that for no node, , you can set for all nodes except for which . This is because any such represents a minimal cut
   Max-flow min-cut theorem
   In optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the source to the sink is equal to the minimum capacity which when removed in a specific way from the network causes the situation that no flow can pass from the source to the...
   
   in the graph, and no more flow will go from the nodes to the nodes . If was not a minimal cut, there would be an edge such that , and . But then would never be set higher than , contradicting that and .