Discovering the Maxflow Mincut Theorem: A Comprehensive and Formal Approach | by Daniel García Solla | Aug, 2023


(A={S,V2}, B={V1,V5,V3,V4,T}) cut (Image by author)

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.

Image by author

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.

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;

Image by author

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.

Image by author

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.

Image by author

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.

Image by author

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.

Image by author

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.

Image by author

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.

(A={S,V1}, B={V2,V5,V3,V4,T}) cut (Image by author)

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:

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.

Sample (A={S,V1,V4}, B={T,V2,V3}) cut (Image by author)

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.

Image by author

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).

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



Source link

Leave a Comment