Mincut Problem
An s-t cut is a cut with \(s\) in one set and \(t\) in the other. Call the sets \(A\) and \(B\).
Given a digraph, with positive edge weights (referred to as capacity), and a source \(s\) and target node \(t\), we define the capacity of the cut to be the sum of the capacities of the crossing edges from \(A\) to \(B\) (note: the edges are directional - we don’t care about crossings from \(B\) to \(A\)).
The goal is to find the minimum capacity cut. This is useful in isolating a group of people (e.g. if you want to cut off the Internet).
Max Flow Problem
Assign to each edge not only a capacity, but a flow, such that the flow is non-negative, but not greater than the capacity. This assignment is called the \(s-t\) flow.
We require that for each node (except \(s\) and \(t\)), the sum of the flows for incoming edges must equal the outgoing sum (no sources or sinks other than the two nodes).
The value of a given \(s-t\) flow is the sum of all the flows into \(t\).
(We assume no edges point into \(s\), or out of \(t\)).
The problem is to find the flow that maximizes this number.
A use case is if one wants to get the maximum amount of aid to a region.
Duality
The mincut and max flow problems are actually duals of one another.
Ford-Fulkerson Algorithm
Set the flow to be 0 for all edges.
An augmenting path is a path from \(s\) to \(t\) such that:
- You can increase flow on forward edges (none of the edges in the path is at capacity).
- You can decrease flow on a backward edge (none of the backward edges has 0 flow).
What is a backward edge? If we have an edge from \(u\) to \(v\), a backward edge is an imaginary one from \(v\) to \(u\) (need not exist in the network). Conceptually, it just means that if the edge from \(u\) to \(v\) has some flow, we can reduce that flow in order to clear up bottlenecks and allow flow from other nodes.
In the image shown, the capacities are 15, 8 and 10, and the flows are 10, 0 and 10. So all that is flowing from A to C is flowing out of C and there’s no room to add anything from B.
If we wanted to, we could add, say, 6 from B to C, but then we’d need to reduce the flow from A to C by the same amount (bringing it to 4). In this case, the edge from C to A is a backward edge. It’s as if we’re inserting 6 from B, and taking it out of C into A.
The algorithm is that as long as an augmenting path exists, use it to increase the overall flow. At some point you won’t be able to find an augmenting path (all possible paths either have a full edge or an empty backward edge that you cannot use to reroute).
Questions:
- How can we compute a mincut from this?
- How can we find augmenting paths?
- If the algorithm terminates, is the flow maximized?
- Does the algorithm always terminate? (Guaranteed if the edge weights are integers)
Max Flow Mincut Theorem
The net flow across a cut \((A,B)\) is the sum of the flows of the crossing edges from \(A\) to \(B\) minus the sum in the other direction.
Flow Value Lemma: Let \(f\) be the flow of a digraph and \((A,B)\) be any cut. Then the net flow across \((A,B)\) equals the value of \(f\).
This can be seen by realizing that there are no sources and sinks other than the \(s\) and \(t\) nodes. More formally, prove by induction. Let \(B=\{t\}\) Then it’s trivially true. This is the base case. For the inductive step, if it’s true for a given \((A',B')\), then moving a node from one set to the other cannot alter the overall flow from \(A'\) to \(B'\). I’m handwaving here, but thinking formally, if a node \(u\) moves from \(B'\) to \(A'\), then there are two cases: If none of the original crossing edges involved \(u\), and if some did. In the former, all the edges involving \(u\) become (new) crossing edges, but their sum must be 0 (from equilibrium). In the latter case, let \(\{a_{i}\}\) be all the crossing edges from \(A\) to \(B\) involving \(u\), and \(\{b_{i}\}\) be all the crossing edges within \(B\) involving \(u\). Once you move \(u\) to \(A\), the crossing edges involving \(u\) now become \(\{b_{i}\}\). But from equilibrium, the sum of all flows in edges in both sets must be the same.
Weak Duality: The value of flow \(f\) is less than the capacity of any cut \((A,B)\).
Theorem: A flow \(f\) is a max flow iff there are no augmenting paths. The value of the max flow is the capacity of the mincut.
Proof: It follows from the equivalence of these 3 statements:
- There exists a cut whose value equals the flow of \(f\).
- \(f\) is a max flow.
- There is no augmenting path with respect to \(f\).
1 implies 2: If such a cut exists, then the value of any other flow must be less than the capacity of this cut! Hence, this is the maximum possible flow.
2 implies 3 from the contrapositive: If a path exists, then we can increase the flow.
3 implies 1: Let \((A,B)\) be a cut such that all the nodes connected to \(s\) in \(A\) have no full forward or empty backward edges. \(t\) must be in \(B\) (as there is no augmented path). Now the capacity of this cut is the net flow across the cut as all crossing forward edges are full (backward edges are empty). But this is the flow of \(f\) by the flow-value lemma.
Computing the mincut From the Max Flow
Let \(A\) be the set of all nodes connected to \(s\) with no full forward or empty backward edges. This cut forms the mincut.
Question: Why?
Analysis
If we assume all the capacities and flows are integers, then the number of augmentations is bounded above by the value of the max flow (as increments to the flow can only be in integral amounts). This guarantees termination of the algorithm.
| Augmenting Path | Max Number of Augmenting Paths | Implementation |
|---|---|---|
| Shortest Path | \(0.5NM\) | BFS |
| Fattest Path | \(M\ln(MU)\) | Priority Queue |
| Random Path | \(MU\) | Randomized Queue |
| DFS Path | \(MU\) | Stack (DFS) |
No proof of these bounds given, and in practice is often a lot lower. \(U\) is the maximum capacity?
Implementation Details
It’s convenient to consider the residual graph. Construct this graph as follows:
- For all forward edges that are not at full capacity, replace with an edge whose weight is the remaining capacity. And create an edge in the opposite direction with the weight of the flow of the forward edge.
- For all full forward edges, do as above but as the forward edge weight is 0, simply don’t draw that edge.
- Similarly, if the flow is 0 in the original graph, don’t bother putting a reverse edge of weight 0.
In this residual graph, simply find a directed path from \(s\) to \(t\). Here you can use BFS, etc.
In practice, the push-relabel method works quite well.
Applications
Bipartite Matching Algorithm
As an illustration, say you have \(N\) people, applying to \(N\) companies. Each company gives some people job offers. Is it possible that each person gets a job and each company gets a new employee?
Converting this into a max flow problem is straightforward. Introduce nodes \(s\) and \(t\), and connect all employees to \(s\), and all companies to \(t\). Let the capacities of these edges be 1. Now connect an employee to a company if the company offered them a job, and let the capacity be infinite.
Now any augmenting path must go through exactly one employee and exactly one company. Furthermore, as the capacity is 1, an employee cannot be part of 2 augmenting paths (same goes for the companies).
If the max flow is \(N\), then you’ve found a perfect matching. If it is less than \(N\), then you cannot get a perfect matching.
Baseball Elimination Problem
Say you have \(N\) teams. Each has won \(w_{i}\) games, and each has \(r_{i}\) games left to play. The question is, can we prove that some team has no chance of coming on top of the league (assume a point per win and no ties)?
Let’s take the example of a league with 5 teams (numbered from 0 to 4) and we’re considering team 4. Look at the graph below:
Note the following:
- The capacity from the source to the game nodes is the number of games remaining between those 2 teams.
- The edges from the games to the teams has infinite capacity.
- The capacity from the teams to the target is the number of more games team 4 can win than team \(i\). This is assuming team 4 wins all the remaining games. In other words, team \(i\) has to win this many more games to tie with team 4 if team 4 wins all remaining games.
Team 4 is not eliminated if and only if all edges from \(s\) are full.
Assume we have a max flow. If all edges leaving from \(s\) are full (which means all remaining games have been played), then that means the edges going to the sink have not “overflowed” - they either have some capacity or are all full. If they have some capacity, that means those teams did not beat team 4 in number of points and lag behind. If the capacity is 0, it means they tied with team 4.
Conversely, assume some edges pointing from \(s\) are not full but we have maxflow. This can only happen if some edges to \(t\) are full (those teams are tied with team 4). As an example, if the edge from \(s\) to \(0-1\) is not full, then the edges from 0 and 1 to \(t\) must be full (otherwise we have an augmenting path). This means both teams 1 and 0 are tied with 4, but they still have some more games to play with each other. In the next game, whoever wins will be ahead of team 4. Hence, if team 4 is not eliminated, all edges from \(s\) must be full.
What if \(w_{4}+r_{4}-w_{i}\) is negative to begin with? Well, we can’t have negative capacity. But in words, this simply means that team \(i\) already has more wins than team 4 can possibly achieve, and so if our graph has a negative capacity, then team 4 is eliminated from the get go.