Discovering the Maxflow Mincut Theorem: A Comprehensive and Formal Approach
Introduction
In the domain of network flow optimization, the Maxflow Mincut Theorem stands out as a remarkable mathematical milestone. Its elegance holds the key to solving complex optimization problems concerning the flow of fluids or resources through networks composed of nodes interconnected by edges. Its applications include a broad range of systems, from transportation networks to communications infrastructure, where efficient flow management is essential. By understanding this theorem and the fundamental concepts behind its mathematical articulation, you can unlock the riddles to maximizing resource utilization and reaching optimal performance in a variety of practical scenarios.
In this article, we aim to simplify and make the theorem approachable for all readers. We will guide you through its historical development, outlining its roots from early formulations that will allow us to appreciate the contributions of prominent minds that paved the way for this theorem and its entire mathematical study field. Moreover, we will delve into the real-world applications of the Maxflow Mincut Theorem. From designing efficient transportation systems to tackling image processing tasks, its versatility seems limitless. By exploring its practical implications, you will witness the theorem's profound impact on diverse fields and industries.
Finally, the goal is to provide you with a comprehensive explanation that matches simplicity and formality. No prior expertise in advanced Mathematics is required, although some knowledge of graph theory and discrete mathematics (logic and set theory) can help significantly; all you need is a curious mind and a willingness to unravel the utility of this exceptional theorem.
History
The Maxflow Mincut Theorem was first introduced by Ford and Fulkerson in 1956 in their seminal paper "_Maximal flow through a network", with the collaboration of other relevant mathematicians, such as Claude Shannon,_ responsible for the development of information theory. The theorem states that the maximum flow in a network is equal to the minimum capacity of a cut, where a cut is a partition of the network nodes into two disjoint sets, and its capacity is the sum of all edges' capacity crossing the cut. Since then, this theorem has become a cornerstone of flow network theory.
However, the introduction of this theorem comes along with other key scientific contributions such as the _Edmonds–Karp, Ford–Fulkerson, or Dinic's_ algorithms, which all serve the common task of finding the maximum flow that can be passed through a network with source and sink. Similarly, by means of the Maxflow Mincut Theorem, this value matches with the minimum cut that divides the sink from the source. Moreover, we can utilize the algorithms' internal computations to identify the set of edges that constitute the minimum cut, as we will explore further.
Flow Networks
Therefore, to simplify the explanation of the theorem that follows, we will first get to know the fundamentals and unmissable concepts about flow networks in graph theory.
As you can see in the above example, a flow network is a weighted, directed multigraph used to represent a network-structured object or system in which a certain amount of resources, measured in what is referred to as "flow", needs to be conveyed or moved from one or more points "source" (represented as the S node) to one or more other nodes called "sink" (T node). Although, this particular example doesn't display the property of multigraph, as there's only one edge between two nodes.
To achieve the representation of such a template, the flow network has weights associated with every edge. In this context, the weighted edges model a physical/logical connection between several points of resource (flow) exchange, where the real positive value of weight stands for its Capacity (max flow supported). Above, you can see the capacity depicted at the right side of each edge label, as well as the current flow passing through, which in this case is 0.
Besides each edge's capacity, the crucial metric that defines the rate at which resources traverse every edge per unit of time is the flow. You can think of it as the traffic on a road or the amount of water through a pipeline. Therefore, generated in the source nodes or supersource node if all network's sources are connected to a master source flow generator and taken to the sink nodes or supersink if the similar construct is present on sinks, we can define the flow as a function f:E→R that takes in an edge (u,v) belonging to the set of graph edges E and outputs its current flow in time f(u,v), which is a real positive value.
Therefore, if we compute the above expressions for all the corresponding sources S or sinks T of the flow network, we can obtain the total amount of flow going through the graph.
To guarantee the flow adhesion to the network's constraints, it must satisfy two fundamental properties:
- Capacity Constraint: The flow passing through any edge cannot exceed its capacity. Formally, if the capacity of an edge is denoted as "c(u, v)," and the flow through that edge is "f(u, v)," then it must satisfy the condition 0 ≤ f(u, v) ≤ c(u, v) for all edges (u, v) within the network. Simply put, we can't push more flow through an edge than its capacity establishes.
- Flow Conservation: At every node (excluding the source and sink nodes), the total flow entering the node must be equal to the total output flow.
This ensures that the flow continues without interruption and does not accumulate or dissipate within the network, despite you can allow flow accumulation if your system requires it. Mathematically, for every node "u" and its neighboring nodes represented and clustered by the supernodes "v and w," the flow conservation property is expressed as:
Lastly, note that the flows can cancel each other, since if flows f1(u,v) and f2(v,u) coexist between 2 nodes u and v, then decreasing f1(u,v) is equivalent to increasing f2(v,u), as they have opposite directions.
Residual Networks and Augmenting Paths
Here we will introduce two new and more sophisticated concepts that will be highly helpful in finding maximum flows by using the previously mentioned algorithms.
The first of these is the difference between an edge's capacity and its flow at a given time, called residual capacity and denoted as:
With that property in mind, we can go ahead and define a particular type of flow network referred to as a Residual Network, where the only difference with a standard network is the redefined capacity for its edges. A residual network counts with the function cf defined above that maps the set of edges, along with their respective capacities and flows, to the corresponding residual capacity.
In this example, you have a network populated with a specific flow function for all its edges in the upper graph. Hence, the residual network turns out to be the one below whose edge labels contain the residual capacity that can be sent according to the direction of the corresponding edge and the amount of flow in the opposite direction that could be delivered in case of undoing a flow augmentation action (remember the flow cancellation property, which can be useful in situations where the network has some symmetry).
Here the flow achieved through the network can be computed with the source or sink formulas as seen before, which in this case is 7 units of flow distributed in 4+3 outgoing units from S or equally 4+1+2 incoming units in T. However, if we consider the (v5, v1) edge in the reverse direction (or bidirectional), there is the possibility of sending 2 more flow units along the path S-V1-V5-V4-V3-T, which would increase the total amount of flow and become the largest available for the given network. Subsequently, after having derived the residual networks, there is the possibility that in one or more paths that connect the source with the sink, all the edges have a residual capacity greater than 0. In other words, there are paths in which we could transport flow from a source to a sink, in the case that there are several sources or sinks.
Within this context, such paths underlie the algorithms used to solve flow maximization or cost minimization issues and are named Augmenting Paths. To understand why, in the above network, we can see how the established flow leads to the existence of an augmenting path whereby 2 units of flow can be transported from S to T. Consequently, the actual flow function over the network does not provide the maximum transportable flow through it, which is one of the problems faced by the Maxflow Mincut theorem that we will discuss later.
As a result, if we increase the flow through the displayed path, we will be able to ensure that the resulting flow is maximal with a value of 9 units since there won't be any other path to increase the network flow. Finally, prior to introducing the theorem, it is important to bear in mind that to find the maximum flow of a network, algorithms such as the Ford-Fulkerson one use an intuitive procedure _(greedy) that starts from a residual network with no flow at all and proceeds to find augmenting paths (with the help of residual edges or opposite direction flows) while increasing the flow as determined by these paths. Thus, once there are no more paths to be discovered that increase the flow, it can be assured that the flow reached is the maximum, i.e., that there is no faster way to move resources from S to T_ due to a lack of capacity on some edges or even a lack of edges in the network.
Another way to think of this procedure is to consider the amount of flow added per iteration. For an arbitrary augmenting path, the highest amount you can add is given by the edge with the least residual capacity since it comprises a bottleneck for the flow out of S. Due to its ability to limit all the potential flow along an augmenting path, such a Bottleneck Edge is key in situations where we need to maximize flow.
For instance, considering the upper simple flow network (residual) with only one augmenting path available, we can clearly identify the bottleneck component of the edge (v2, v3), which sets the maximum flow of the whole path (and in this case the network) to 3. After increasing the flow by 3 units as the path suggests, there is no augmenting path to increase the flow further, so the maximum flow is concluded to be reached. However, another way to ensure the validation of the resulting flow is to focus on the bottlenecks within the network; if every path between S and T has a null bottleneck value, i.e., its maximum residual capacity equal to 0, which is equivalent to the non-existence of augmenting paths, no more flow can be added and the current will be considered as maximum as seen above.
To settle the question regarding bottlenecks; we should highlight that maximum flow can also be expressed as the sum of all the augmenting path's bottlenecks used to find the maximum flow via Ford-Fulkerson-like algorithms since each path adds as much flow as determined by its corresponding bottleneck.
Flow Network Cuts
The last part we will cover concerning the basis of flow networks will be Cuts, a fundamental component of the Maxflow Mincut theorem, and a key concept in understanding the previous sections due to e.g. the link between bottlenecks and partitions of a flow network.
First of all, let's start with its definition; a cut is a partition of the network nodes where the source node S is in a set A and the sink T is in another set B disjoint to the previous one.
Neither A nor B sets can be empty, as they must contain the source(s) and sink(s), respectively. Therefore, if the network is connected, there will be edges that perform the connection functionality between the nodes of A and B bidirectionally. Also, these edges are contained in another set named cut-set, although only those whose origin is a node in A and ends in B are taken into account, i.e. edges able to transport flow in the correct direction.
As an example, above you can see the simplest cut we can apply to the graph, resulting in a partition of the vertex set V as the union of the sets A={S} and B={V1,V2,V3,V4,V5,T}. As the unique network source remains isolated in a set, we can understand more precisely the concept of a cut and its subsequent properties. Typically, the cut is represented as a line that seeks to enclose one of the two sets A or B, indistinctly. Furthermore, the dividing boundary crosses multiple edges that are part of the cut-set, in both directions. These edges are used to determine the flow and capacity of the cut, which are essential components when establishing a relationship between a network's arbitrary cut and flow. This is crucial in proving the theorem presented in this article.
On the one hand, the flow through any given cut is defined as the sum of all the edges carrying flow in the direction A-B, minus the flow of the edges going in the opposite direction from set B to A.
However, the flow does not offer significant value in this context, as it is limited by the capacity of the cut. For this reason, we can also define the capacity of a cut in a similar way as for the flow, with the difference here that only the first term of the above formula is taken into account, i.e., the capacity of the edges that are capable of carrying the flow from S to T, without having to subtract any other edge value.
Once we have formally presented the concept of flow and capacity in cuts, it becomes necessary to consider some examples for simplifying these ideas as much as possible and to understand their rationale in this area.
First, let's examine each set's vertices, leaving A={S,V5,V4} and B={V1,V2,V3,T}. Since the network has already been assigned a flow, then the cut flow won't be zero and will be determined by the sum of the flows on the edges connecting set A to B.
Additionally, its capacity is obtained from the same previous edges and their respective capacities, constituting the maximum flow that could transit the cut.
In this interesting last sample cut, we can observe how a cut does not have to be a split where the vertices of both sets comprise connected components, that is, each set can contain any node as long as the basic constraints of a cut are met.
Also, this example is particularly helpful in understanding the relationship between cuts and flow, providing a solid grounding before tackling the theorem. First, be aware that according to the cut definition, the resulting network (after the cut) is disconnected with respect to s-t. That means the capacity of such a cut is computed as the sum of all edges leading from the source assembly to the sink. In the most basic case of isolating the single source of flow, the capacity of the cut will exceed or equal the maximum flow of the network. However, in the previous examples, it can be appreciated that by inserting more nodes with outgoing edges, the capacity of the cut inevitably increases since there are more edges than strictly required to reach the maximum flow, i.e., the edges of the source are the ones that determine, in the case of bottlenecks, the flow that will subsequently go over the network.
Theorem Statement
Our primary objective in addressing a flow network optimization challenge is to determine the maximum attainable flow that can be conveyed from source to sink. This must be accomplished while adhering to the limitations on capacity, flow conservation, and ensuring the achieved flow is actually maximum. So, the step we will take in addressing the theorem will be to constrain that value with an upper bound that can be calculated roughly similar to the flow and thereby confirm its correctness.
Initially, it should be highlighted that such an upper bound happens to be a cut, which fulfills the property of being the one with the least capacity. As the main lemma of the theorem, it may not be entirely clear, so let's introduce and prove two simpler ideas;
The first one involves proving the above equality between the flow through any given cut and the total network flow, which in turn matches the source-generated flow. For this purpose, we can assume the initial proposition as true while applying the induction method to the set A of any cut, with A={S} as the base case, and then use the previously mentioned principle of flow conservation for nodes different from S or T. But since this would be complex to elaborate, we will opt for a simpler, although very similar, approach.
Note that the previous flow value along the proof can have any allowed value.
1- Flow Definition: In the initial step, we start with the total flow value for any given flow function f in a network and one of its possible definitions. Here, by having as a reference the source node S, which is the smallest possible set A for any network cut, we match the value of the flow to the flow generated by S minus the incoming flow into S since sometimes there may be a certain amount of flow returning to S.
2- Flow Conservation Property: After considering the network flow as the total flow generated by the source S, we apply the flow conservation principle whereby all nodes except s-t must propagate all the flow they receive, resulting in zero flow contributed to |f| by subtracting the outgoing minus the incoming flow. Now, if we take any cut (A,B), the total flow contributed by the nodes v within set A except the one that generates the flow {S} will be zero, satisfying the equality we had before.
3- Flow Trough Cut: Finally, we arrive at an expression where we add up all the outgoing flow from the nodes of A except S in the second term and S's own outgoing flow in the first term, subtracting the corresponding incoming part from all the previous nodes. This corresponds to the aforementioned definition of cut flow, and therefore we can conclude as a consequence that all the existing flow through a network will necessarily match the flow through any given cut.
The second proposition we will prove concerning the Maxflow Mincut theorem comprises an inequality that upper bounds the value of any flow in a network with the capacity value for any given cut.
1- Alternative Flow Definition: Using the previous result regarding the flow of any cut, we can equal an arbitrary flow |f| to the flow through an arbitrary cut (A,B).
2/3- Flow Bounding: In the second step, we establish an inequality that dispenses the second term that models the incoming flow in set A, leaving only the outgoing flow of the edges that carry flow from A to B. After removing such a term, the result will always be greater than or equal to the previous one since if there is no edge that returns flow from B to A, the sum of the remaining edges flow from A to B will not decrease.
Then, we can simply augment the value of the inequality by setting the flow of outgoing edges from A to be less than or equal to the capacity of those edges. The validity of this inequality is given by the capacity constraint appearing on all network edges.
4- _Weak Duality:_ After matching the capacity sum of all the outgoing edges of set A with the cut capacity due to its definition, it can be concluded that for any given flow and cut in a network, the flow will always be smaller or equal to the cut capacity, which turns out to be the starting point of the theorem we are about to prove. Also, if we try to maximize the flow, we will reach a point that can be met by minimizing a cut capacity, establishing a weakly dual relationship where there is no certainty that a minimum capacity cut equal to a maximum flow will always exist.
At this point, after having reached the weak duality prior to the Maxflow Mincut theorem, we can deliver a statement that is easier to comprehend and verify.
As already mentioned, the theorem holds via _Strong Duality_ that the maximum flow in any network matches the least-capacity cut attainable. In contrast to the former weakly dual result, this theorem ensures that the flow maximization dual is exactly equal to the minimization of any cut capacity, removing the possibility of having a difference between the two results and granting a strongly dual condition on the lemma.
Before proceeding with its demonstration, we should highlight a use case for the theorem. Here, the maximum flow has a value of 7, which equals the sum of each outgoing cut edge's capacity. Note that these edges carry flow at their maximum capacity, which, in a minimum capacity cut such as the one shown, causes these edges to be bottlenecks, i.e., the cut-set itself acts as a bottleneck of the global network flow. To condense the explanation of this idea, you will find below a resource to help you understand it:
What's an intuitive explanation of the max-flow min-cut theorem?
Proof
If we want to prove that the maximum network flow equals, in all cases, the minimum capacity cut-off in a network, we will use 3 propositions that must be equivalent for the theorem to be true.
There exists a cut (A, B) that satisfies |f|= cap(A, B).
Flow value |f| is maximum.
There is no augmenting path in the flow network.
In order to show that all statements are equivalent, we will demonstrate the logical implications 1⇒2⇒3⇒1. Meaning that we can infer any statement from any other statement. In the case of 1⇒2, it can be easily verified using the weak duality shown earlier. Then, considering that any flow is smaller than the cut with the least capacity, if we assume that there exists a flow equal to the capacity of an arbitrary cut (1), the weak duality tells us that this capacity is the upper bound for any given flow and therefore the resulting flow, coincident with that bound, is maximal (2).
Proceeding with 2⇒3, the simplest way to verify it is to take the contrapositive ¬3⇒¬2. Then, it suffices to take an arbitrary flow |f| as an example, in case there was an augmenting path s-t ¬(3) that could transport flow, |f| could be increased across the corresponding path, which implies that |f| was not originally the maximum flow ¬(2).
Finally, the most challenging step in this demonstration is 3⇒1. First, we start by assuming a flow |f| in which the network has no augmenting paths. Furthermore, we define a set A containing all vertices reachable from S in the residual network. That is, A contains all vertices to which there exists a path from S in the residual network, and at the same time, all residual edges of that path are non-zero. Through these definitions, we can be certain that S is in A since it is self-reachable, and since there are no augmenting paths, T is not reachable in the residual network from S, so we know that at least one node (T) is not in the set A. Then, if we insert T into a different set B, then we have that the pair (A, B) satisfies all the criteria to be a valid cut in the network.
At this point, we must realize two things about the cut (A, B). On the one hand, the flow through the cut in the S-T direction must be equal to its capacity. Because by the previous definitions and assumptions (3), the only possibility that they were not equal lies in the reachability of the nodes of B, so if any of them were reachable from S in the residual network, causing the flow on the cut edge not to reach its full capacity, the node would have to be inside A instead of B, which is a contradiction. On the other hand, the flow in the other direction of the cut turns out to be zero owing to the same reason as before, i.e., if it were not zero, there would be an edge in the residual network in the direction A-B (residual edge flow represented with negative sign) that would reach the node at B and cause the contradiction.
Lastly, the only thing left to do is to match the network flow to the cut flow, which was demonstrated previously, remove the term of the flow into the cut since its null, and use the cut capacity definition to conclude that the flow |f| equals the resulting cut capacity (3⇒1).
Applications
The Maxflow Mincut Theorem has numerous applications in various fields. However, to keep it short, we will simply mention some essential aspects of the use cases, along with more detailed resources to help you understand them correctly.
Ford-Fulkerson/Edmonds–Karp Algorithms
As a first consequence, the findings and results provided by the theorem, in conjunction with other ones such as the integrality theorem, lead to and support the correctness proof of a series of algorithms oriented to calculating maximum flow.
The most significant of these, and the one we've already talked about, is _Ford Fulkerson's algorithm, a greedy approach that increases the flow by seeking s-t augmenting paths. However, the most basic version of the algorithm has no guarantee to terminate or converge to the maximum flow in certain situations with very specific inputs (such as working with real or irrational numbers and their representation) due to the way it chooses augmenting paths. This also influences its time complexity, which is O(|E| |f|), meaning that in the worst case, the algorithm needs to traverse all edges of the network for each (at least one)_ unit of flow contained in the maximum to be reached.
Then, with the aim of improving the previous version, which was the first one created to solve problems of this kind, the way of calculating augmenting paths was improved. In such a way that, while the Ford-Fulkerson version used depth-first search (DFS), which computes random paths to T, the improved Edmonds-Karp variant is implemented using the breadth-first search (BFS) algorithm to find augmenting paths. So, with the aim of choosing at each iteration the augmenting path with the fewest possible edges, the algorithm has a termination guarantee with respect to the previous one, in addition to a change in the time complexity in the order of O(V E²).
Nevertheless, with these and similar algorithms, it is possible to compute not only the maximum flow in a network but also the minimum cut whose capacity equals its value. The procedure is quite simple; after calculating the maximum flow in all the edges of a network, according to the Maxflow Mincut theorem, the nodes accessible from S in the corresponding remaining residual network form the set A of the cut we are looking for, being the remaining nodes in B and leading to the resulting minimum capacity cut (A, B).
Finally, it should be noted that the field of study of maximum flow algorithms is much larger than what is shown here. Therefore, if you wish to continue learning, here you have a resource that addresses these algorithms, as well as their implementations, in more detail.
Practical Use Cases
Nearly all the systems we interact with in our lives have some potential to be modeled (at least in part) by flow networks, which turns them into a crucial tool for addressing complex scalability problems. Likewise, as the possibilities are broad, only some of them will be mentioned here that provide a direct relationship with the fundamental concepts.
Initially, all the transportation systems, ranging from road networks and public transit systems to airline routing and cargo distribution, can be represented as flow networks. As a result, we can analyze traffic patterns, optimize routes, and enhance overall efficiency. This is particularly crucial in urban planning, where managing the flow of people, vehicles, and goods is essential to prevent congestion and ensure smooth operations. Moreover, not all of these use cases are entirely beneficial; for instance, flow networks can also model a country's railway system, which may be targeted, in case of military conflict, for attacks that should be as strategically optimal as possible. You can learn more about this specific application in this resource.
Despite other transcendental implementations in telecommunications, energy distribution, or even healthcare, we will focus on one more closely associated with computer science, specifically with the field of computer vision, which has achieved significant breakthroughs. In image processing, the main deployment of flow networks relies on _Image Segmentation algorithms, responsible for dividing an image into segments or regions that correspond to objects, subjects, or distinct areas necessary to spot, which maybe can't be distinguished by the human eye. In this context, flow networks bring their prowess by modeling the relationships between pixels as a network, where the edges represent the flow of likelihood values for similarity/dissimilarity between neighboring pixels. Furthermore, it is also worth mentioning the applications in comparable scopes, such as Machine Learning models_, in which the flow concept is used to optimize specific learning, generative, or classification tasks.
Conclusion
This article has covered a minor fraction of the mathematical domain of flow networks, as well as proving and simplifying one of its fundamental theorems. However, since it is a subject with a vast number of applications, particularly in the world's system of consumption, transportation, and population management, it is useful to continue enlarging the theory and deepening the knowledge about these applications. For this purpose, the most efficient resources for observing more advanced formalizations of the theorem, as well as understanding step-by-step the algorithms mentioned in this article and learning new concepts about certain applications of flow networks, are the following:
https://www.cs.upc.edu/~mjserna/docencia/grauA/P20/MaxFlow-fib.pdf
https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Introduction_to_Network_Flow.pdf
