Push–relabel maximum flow algorithm

Imagine moving water through many pipes.

We want to move as much as we can. One way is to use a push and relabel method. First, we push the water to a new spot.

If the water gets stuck, we change its height. This is called a relabel. We do this until the water flows well.

This way is very fast and smart. It helps us find the best path for the water.

Imagine water moving through a network of pipes. We want to find the maximum flow. This means finding the most water that can move from a source to a sink.

One smart way to do this is the push-relabel algorithm. This method uses two main steps. First, it uses a push operation. This moves flow from one point to a neighbor.

Sometimes, the flow gets stuck. When this happens, the algorithm uses a relabel operation. This changes the height, or distance label, of a point.

Changing the height helps the flow move to the right place. This algorithm was made by Andrew V. Goldberg and Robert Tarjan in 1986. It is very efficient. It is much faster than the Edmonds-Karp algorithm. It can even find the lowest cost for a flow. The method works by keeping a preflow. A preflow is when more flow enters a point than leaves it. The algorithm fixes this until the flow is perfect.

Imagine a network of pipes carrying water from a source to a sink. We want to find the maximum amount of water that can flow through. This is a puzzle in mathematical optimization. One smart way to solve it is the push-relabel algorithm. This method is very efficient at finding the answer. It is often faster than the Edmonds-Karp algorithm. It can even be used to find the lowest cost for a flow.

The algorithm works using two main steps called push and relabel. It starts with something called a preflow. In a preflow, more water might enter a point than leaves it. This creates an excess at that point. To fix this, the algorithm uses a push operation. A push moves flow from an active node to a neighbor. This only happens if the neighbor is at a lower height.

Sometimes, the flow cannot move forward because the neighbors are too high. When this happens, the algorithm uses a relabel operation. This changes the height, or distance label, of the node. The relabel step increases the height of the node. This makes it possible to push the excess flow to a neighbor. The algorithm keeps doing these steps until no more excess remains.

This idea of using a preflow was first thought of by Alexander V. Karzanov. He published his work in 1974 in Soviet Mathematical Dokladi 15. Later, Andrew V. Goldberg and Robert Tarjan designed the push-relabel algorithm. They first presented it in November 1986 at a big meeting called STOC '86. They officially published it in October 1988 in the Journal of the ACM. They also showed how to use it in parallel systems.

Math helps us understand how things move through a system. This algorithm uses height labels to guide the flow. A node is called active if it has extra flow to move. The algorithm uses these labels to make sure the flow reaches the sink. If it cannot reach the sink, the flow eventually moves back to the source. This ensures the final result is the true maximum flow.

In mathematical optimization, the push-relabel algorithm is a highly efficient method for calculating maximum flows within a network. A flow network is a system of nodes connected by edges, each with a specific capacity. The goal is to determine the greatest amount of flow that can move from a starting point, called the source, to an endpoint, called the sink. Unlike the Ford-Fulkerson algorithm, which searches for long paths from the source to the sink, push-relabel works locally. It manages flow by moving it between neighboring nodes using two primary operations: push and relabel.

The algorithm relies on a concept known as a preflow. In a standard flow, the amount of flow entering a node must equal the amount leaving it. However, a preflow allows more flow to enter a node than leaves it. This creates an excess, which is the difference between the incoming and outgoing flow. A node is considered "active" if it has a positive excess. The algorithm's job is to gradually convert this preflow into a true maximum flow by eliminating all excess at every node except the source and the sink.

To guide the flow, the algorithm uses distance labels, often called heights. Each node is assigned a non-negative integer label, denoted as l(u). These labels must follow specific rules to remain valid. For example, the label of the source is set to the total number of nodes in the graph, while the sink is set to zero. These labels ensure that flow only moves from a higher node to a lower node. An arc is called "admissible" if it connects a node to a neighbor with a label exactly one unit lower.

There are two main operations used to manage the preflow. The push operation moves flow from an active node to an adjacent node through an admissible arc. If the push uses up all the remaining capacity of an arc, it is called a saturating push. If it simply moves some of the excess, it is an unsaturating push. When an active node has excess but no admissible outgoing arcs, the relabel operation is triggered. Relabeling increases the node's height to the minimum value required to create at least one admissible arc.

The history of this method involves several key mathematical discoveries. The concept of using a preflow was originally conceived by Alexander V. Karzanov, who published his findings in 1974 in Soviet Mathematical Dokladi 15. Later, Andrew V. Goldberg and Robert Tarjan designed the specific push-relabel algorithm. They first presented their work in November 1986 at the STOC '86 symposium. They officially published the algorithm in the Journal of the ACM in October 1988. Their work also included methods for implementing the algorithm in parallel and distributed systems.

Analyzing the efficiency of the algorithm requires looking at the complexity of its operations. The generic version of the algorithm has a strongly polynomial time complexity. This makes it asymptotically more efficient than the Edmonds-Karp algorithm. Specifically, the number of relabel operations is bounded by the number of nodes multiplied by the maximum possible label. Saturating pushes are also limited because each one requires subsequent relabeling to repeat. By using advanced data structures like dynamic trees, researchers can even achieve subcubic time complexity, though this is often less efficient in practice.

One of the most powerful versions of this algorithm uses the highest label node selection rule. This variant is often regarded as the benchmark for maximum flow algorithms due to its high empirical performance. The algorithm can also be extended to solve more complex problems, such as computing minimum cost flows. By incorporating distance labels into augmenting path algorithms, developers have created even faster versions.

Ultimately, the push-relabel algorithm is a fundamental tool in computer science and optimization. It demonstrates how local rules, like pushing flow to a lower neighbor, can solve a global problem like finding a maximum flow. The process continues until no active nodes remain, meaning all excess has been pushed to the sink or returned to the source. At this point, the max-flow min-cut theorem guarantees that the resulting flow is indeed the maximum possible.