Push-relabel algorithm

The push-relabel algorithm is a max flow method in Combinatorics that works by moving excess flow through a network and raising vertex labels when flow gets stuck. It finds the maximum flow without searching for augmenting paths.

What is the push-relabel algorithm?

The push-relabel algorithm is a way to solve the maximum flow problem in Combinatorics by working with a preflow instead of waiting for a neat source-to-sink path. A preflow can leave extra flow sitting at vertices, and the algorithm keeps pushing that excess forward until the network settles into a valid maximum flow.

The two moves are exactly what the name says. A push sends flow from one vertex to a neighbor along an edge that still has room and whose height label allows the move. A relabel increases a vertex’s height when it cannot push anywhere useful, which gives that vertex new directions to try.

Those height labels are the control system. They do not measure distance in the usual graph sense, but they act like a guide that prevents the algorithm from cycling around randomly. A push is only allowed from a higher vertex to a lower one, so the algorithm keeps making progress toward moving excess closer to the sink.

This is different from Ford-Fulkerson style thinking, where you keep looking for augmenting paths from source to sink. Push-relabel can work locally, one vertex at a time, which makes it a strong choice for large or dense flow networks. You will often see that local logic in graph theory problems where the network has many edges and ordinary path-based methods would be slow or messy.

A small example makes the idea easier to picture. Suppose a vertex has excess flow but every outgoing edge is full or blocked by the height rule. Then the vertex gets relabeled upward. After that, one of its outgoing edges may become admissible, and a push can move some of the excess onward. The process repeats until no vertex except the source and sink has leftover excess.

The final maximum flow is read from the finished preflow, usually by checking how much flow reaches the sink or by confirming that no active vertex can push or relabel anymore. That is the moment when the network is at its best possible throughput.

Why the push-relabel algorithm matters in COMBINATORICS

Push-relabel matters because it gives you a concrete way to solve maximum flow problems when a network looks too big or tangled for hand-tracing augmenting paths. In Combinatorics, that means it shows up right next to flow networks, min cuts, and proofs that compare different ways of measuring capacity.

It also gives you a different way to think about flow. Instead of focusing only on complete source-to-sink routes, you track local vertex behavior: how much excess is sitting at a node, which edges can accept more flow, and when a vertex needs to be relabeled. That shift from global paths to local moves is a big idea in graph algorithms.

The method is useful for reasoning about why maximum flow algorithms terminate and how their runtime changes with graph shape. Dense networks often make path-search methods feel clumsy, while push-relabel stays organized by using labels to limit wasted moves. If a problem asks you to compare algorithms, this is the kind of advantage you would mention.

It also connects directly to the max-flow min-cut picture. Once the algorithm stops, the absence of any legal push or relabel move tells you the network is saturated in a way that matches the best cut. That connection is the bridge between an operational algorithm and the broader theorem behind it.

How the push-relabel algorithm connects across the course

Flow Network

Push-relabel only makes sense inside a flow network, where edges have capacities and flow starts at a source and ends at a sink. The algorithm updates that network locally, but the capacities of the directed edges still set the limits on every push. If you do not understand the network setup, the push and relabel steps will feel random.

Maximum Flow Problem

This is the main problem push-relabel is trying to solve. The algorithm is one method for finding the largest possible amount of flow that can go from source to sink without breaking capacity rules. When a problem asks you to compute or reason about maximum flow, push-relabel is one of the standard algorithmic tools you can name.

Preflow

A preflow is the starting point for push-relabel, and it is not the same as a final valid flow because vertices can hold excess. That excess is exactly what the algorithm works to remove. If you mix up flow and preflow, the algorithm’s first step and its stopping condition will not make sense.

Ford-Fulkerson Method

Ford-Fulkerson and push-relabel both solve maximum flow, but they do it differently. Ford-Fulkerson searches for augmenting paths, while push-relabel works by pushing excess locally and relabeling vertices. On a problem set, you may be asked to compare them or explain why one might be better for a certain network.

Is the push-relabel algorithm on the COMBINATORICS exam?

A graph theory problem may give you a small flow network and ask what happens after a push or relabel step, or which edges are admissible from a vertex with a given height. You may also need to explain why the algorithm can keep moving without finding full augmenting paths first. The usual move is to track excess at active vertices, check capacity limits, and use the height labels to see which pushes are legal. If a question asks for the maximum flow value, you do not compute it by hand with every possible path, you describe how the preflow settles or identify the sink flow at the end. A good answer shows that you know the algorithm is local, not path-based.

The push-relabel algorithm vs Ford-Fulkerson Method

Ford-Fulkerson and push-relabel both solve maximum flow, so they get mixed up a lot. The difference is the strategy: Ford-Fulkerson searches for augmenting paths, while push-relabel pushes excess flow around locally and uses relabels to open new moves. If a problem asks about height labels or preflows, it is push-relabel. If it asks about augmenting paths, it is Ford-Fulkerson.

Key things to remember about the push-relabel algorithm

• Push-relabel is a maximum flow algorithm that works by moving excess flow through a network instead of searching only for source-to-sink paths.

• The two core actions are push, which sends flow along an admissible edge, and relabel, which raises a vertex’s height when it gets stuck.

• Height labels control the algorithm and keep it moving forward, so it does not bounce around the graph without making progress.

• The method starts from a preflow, not a finished flow, which is why vertices can temporarily hold excess.

• When the algorithm stops, the network is at maximum flow and the result connects directly to the max-flow min-cut idea.

Frequently asked questions about the push-relabel algorithm

What is push-relabel algorithm in Combinatorics?

It is a maximum flow algorithm for a flow network. Instead of looking for full augmenting paths, it keeps track of excess flow at vertices, pushes that excess forward when possible, and relabels vertices when they cannot push anywhere.

How does the push-relabel algorithm work?

You start with a preflow and assign height labels to vertices. If a vertex has excess flow, it tries to push that flow to a lower neighboring vertex with available capacity. If no push is possible, the vertex is relabeled upward so new pushes may become legal.

Is push-relabel the same as Ford-Fulkerson?

No. Both solve maximum flow, but Ford-Fulkerson searches for augmenting paths from source to sink, while push-relabel works locally with excess flow and height labels. They solve the same type of problem with very different mechanics.

Why do height labels matter in push-relabel?

Height labels decide which pushes are allowed and keep the algorithm making progress. A vertex usually can only push flow to a lower-height neighbor, and if it is stuck, relabeling raises its height so it can try different edges.