1. Introduction

The idea of augmenting paths comes up in two different contexts in computer science. These are matching theory and the maximum flow problem. In both cases, we can use augmenting paths to increase the size of an existing solution. This way, the solution gets closer to being optimal.

In this tutorial, we’ll discuss what exactly are augmenting paths. First, we’ll see them in the context of matchings in a graph. Then, we’ll study them in relation to the maximum flow problem. We’ll also briefly discuss some algorithms that make use of augmenting paths.

2. Augmenting Paths in Matching Theory

2.1. Definitions

Before we can talk about what augmenting paths are with respect to matchings, we need a few definitions. A matching M is a subset of the edges of a graph G = (V, E) such that no two edges in M share a common vertex.

If M has the largest size amongst all matchings in G, then we call M a maximum matching. We call a vertex of G matched by M if M touches that vertex. Otherwise, the vertex is unmatched.

On the left below is an example of a matching in a bipartite graph (the red-colored edges represent a matching):

A path in G which starts at an unmatched vertex and then contains, alternately, edges from E-M and M, is an alternating path with respect to M. We call an alternating path that ends in an unmatched vertex an augmenting path.

For the matching above, the path a-a'-b-b'-c-c' is an example of both an alternating path and an augmenting path. This path is highlighted in green on the right.

2.2. How Are Augmenting Paths Used for Finding Maximum Matchings?

We can use an augmenting path P to turn a matching M into a larger matching by taking the symmetric difference of M with the edges of P. In other words, we remove edges from M which are in both P and M. We add/keep all other edges. We can best illustrate this by an example:

The augmenting path we used is shown below:

Here we used the augmenting path a-a'-b-b'-c-c' (shown in green) to augment the initial matching M to obtain a bigger matching M'. The edges ba' and cb' were removed from M and the edges aa', bb', and cc' were added to M. We also kept the edge dd' in M.

We can prove that if we start with any matching and repeatedly augment it by augmenting paths, we’ll always eventually obtain matching of optimal size, i.e., a maximum matching.

This is the key intuition behind any algorithm for finding maximum matchings.

2.3. Algorithms That Use Augmenting Paths to Find Maximum Matchings

Two examples of famous algorithms that use augmenting paths are the Hungarian Algorithm and the Blossom Algorithm. We can use the former to find maximum matchings in a bipartite graph and the latter to find maximum matchings in a general graph. To find an augmenting path, algorithms will typically use a tree search such as depth-first search or breadth-first search, with some minor modifications/additions.

3. Augmenting Paths in the Maximum Flow Problem

3.1. Some Initial Definitions

Let’s look at a few key definitions first. Then we’ll see what an augmenting path is in the maximum flow problem.

A flow networkG = (V, E) is a directed graph in which each edge (u, v) has a nonnegative capacity c(u, v) >= 0. We don’t allow self-loops and c(u, v) = 0 if the edge (u, v) doesn’t exist. Finally, if there exists an edge (u, v) in the network then the reverse edge (v, u) doesn’t exist.

Here is an example of a flow network which contains a flow with a total value of 19:

The edge labels take the form f/c to communicate the fact that an edge has a capacity of c and a flow of f.

There are two special vertices in a flow network; the source s and the sink t. The source can be thought of as a vertex that produces some material, and the sink is a vertex that consumes the material.

We define a flow in a flow network as an assignment of nonnegative real-numbers to the edges of the network such that the values do not exceed the capacity constraints and the principle of flow conservation holds. Flow conservation says that at every node except the source and the sink, the total incoming flow must equal the total outgoing flow.

The total value of a flow f, denoted by |f|, is defined as the total flow leaving the source minus the total flow coming into the source. In the maximum-flow problemwe’re given a flow network G, and we want to find a flow of maximum value.

3.2. Residual Networks

Given a flow network G, the corresponding residual network Gr represents how we can change the flow on different edges of G. For an edge in G with flow less than that edge’s capacity, there will be a corresponding edge in Gr that has a residual capacity of the original edge’s capacity minus the flow on that edge.

If an edge in the original graph is saturated (its flow equals its capacity), then the corresponding edge is omitted from the residual graph as it cannot admit anymore flow.

We can also have edges in the residual graph that are not in the original graph. These are edges that allow an algorithm to send flow back on an edge, thereby reducing the original flow on that edge. If we have an edge (u, v) in G with a certain amount of flow on it, then we’ll have an opposite edge (v, u) in the residual graph with a capacity equal to that flow.

Below is an example of the residual graph Gr for the flow network G shown above:

 

 

If we look at this residual network, we can see the above concepts in action.

For example, we can see that there is an edge in G with a capacity 16 from s to v1 with a flow amount of 11 units. Therefore, we have two corresponding edges in Gr. One edge is a forward edge from s to v1 with a residual capacity of 5. The other is a back edge from v1 to s with a residual capacity 11.

The forward edge represents the fact that we can still send an additional 5 units of flow from s to v1. The back edge communicates that we can send 11 units of flow back from v1 to s (which is the same as reducing the flow going from s to v1).

3.3. Augmenting Paths

Now that we have defined what a residual network is, we can talk about augmenting paths. Given a flow network G, an augmenting path is a simple path from the source to the sink in the corresponding residual network Gr. Intuitively, an augmenting path tells us how we can change the flow on certain edges in G so that we increase the overall flow from the source to the sink.

For example, here is an augmenting path (shaded in red) in the previous residual graph:

 

 

If we treat this network as a flow network, we can think of sending 4 units of flow along this path from s to t. Sending flow along this path in Gr corresponds to increasing and decreasing the flow on particular edges in G. In this case, we can send at most 4 units of flow along the augmenting path in Gr so that in G, we increase the flow by 4 units on edges (s, v2) and (v3, t), and decrease the flow by 4 units on the edge (v3, v2).

This brings up an important point related to augmenting paths. Although an augmenting path increases the overall flow, it can not only increase the flow on an edge; it can also decrease it. It can be easy to think that since an augmenting path augments the flow, it’s only increasing edge flows. But this is not necessarily true.

We can prove that given any flow f in a flow network G and an augmenting path in Gr, augmenting f with this path will give us a new flow in G with a higher value.

3.4. Algorithms That Use Augmenting Paths to Find the Maximum Flow

Perhaps the most well-known algorithm which uses augmenting paths to find a maximum flow is the Ford-Fulkerson algorithm. The intuition behind the Ford-Fulkerson method is simple: while there exists an augmenting path with respect to the current flow in the network, augment that flow using the augmenting path to obtain a new flow. This strategy guarantees that we’ll find a maximum flow because of a famous theorem called the max-flow min-cut theorem, which tells us that a flow has maximum value if and only if there is no augmenting path in its residual graph.

Based on how we find augmenting paths in the Ford-Fulkerson method, we can obtain better running times. For example, we can choose the shortest path with available capacity as our augmenting path in each iteration. Then we’ll get a faster implementation of Ford-Fulkerson. This is called the Edmonds-Karp Algorithm.

Another algorithm for computing maximum flows is called Dinic’s Algorithm. Instead of simply finding one augmenting path in each iteration, it makes use of two important ideas: the level graph and the blocking flow. By finding a blocking flow, Dinic’s algorithm computes all augmenting paths of a particular length. Then it uses this blocking flow to augment the flow.

4. Conclusion

In this article, we have studied what augmenting paths are in the contexts of maximum matchings and maximum flows. We have also briefly discussed some algorithms which make use of augmenting paths.

Comments are closed on this article!