Making Minimal Flow Cuts
The opposite type of network algorithm, a minimal flow
algorithm, also has useful applications. In the minimal flow cut problem (also called "min flow cut"), you need to remove the set of links with the smallest total capacity from the network so that after their removal, no path exists between a given start and end node.
This has some direct physical applications. For example, suppose you need to separate two points on an electrical circuit by cutting the circuit in the fewest possible places. Or suppose you want to know how many bridges you need to cut to send Manhattan floating into the Atlantic.
The minimal flow cut problem is also useful for studying how robust a network is. Suppose you have a computer, phone, electric, or other network. The minimal flow cut between two points tells you how many places the network must fail before you lose connectivity between those points.
|Figure 8. Careful Cuts: The minimal flow cut algorithm separates two nodes by removing a set of links that have a minimal total flow.|
For an example, consider the network shown in Figure 8
. Suppose you want to find a minimal flow cut between nodes 0
. You could separate those nodes by removing the links 0
. Those links have capacities 4
respectively, so the total removed capacity would be 4
Alternatively, you could remove the links 3,1-3,2, 2,2-3,2, and 3,3-3,2. All those links have a capacity of 2, so the total capacity removed would be 2 + 2 + 2 = 6, which is an improvement over the previous solution.
So what's the minimal capacity you can remove to separate the start and end nodes? You might take a few minutes to see if you can find an even better solution before you read further.
It turns out that the minimal flow that you need to remove to separate the start and end nodes is equal to the maximal flow between those nodes. The rightmost image in Figure 7 shows that the maximal flow between nodes 0,0 and 3,2 in this network is 4, so you know that the minimal cut to separate those nodes removes a total capacity of only 4 from the network. (Did you find such a cut?)
In fact, the maximal flow calculation even shows you one way to find the cuts that you need to make. Here's the algorithm:
- Perform a maximal flow calculation.
- Beginning at the start node, traverse the final residual network using links that have residual capacities greater than 0.
- Place all the nodes reached in Step 2 in set A. Place all the other nodes in set B.
- Remove all the links connecting nodes in set A with nodes in set B.
Why does this work? The high-level explanation suitable for managers, history majors, and others who don't want to know all the details is that the maximal flow must pass through a choke point somewhere. There's some place in the network where the flows are restricted to the maximal flow—and that's where you remove links to cut the network.
For a more detailed explanation, suppose you have a total flow of F
moving through the network from the start node to the end node. Now suppose you make any cut that separates the network into two sets A
so the start and end nodes are separated.
Now notice that the net flow across the cut must be equal to the flow F reaching the end node. Flows may move back and forth across the cut, but in the end, F units of flow must reach the end node, so the net flow across the cut must be F.
Now consider the cut produced by the algorithm. First notice that this cut does separate the start and end nodes. If it did not, then there would be an augmenting path through the network from the start node to the end node. Assuming you have completed the maximal flow calculation, there must not be such a path.
That means the net flow across the cut is equal to the maximal flow. But that's only the net flow. What if flows move back and forth across the cut? In that case, this cut wouldn't have the minimum possible capacity. (For a concrete example, suppose the maximal flow is 1 and the flow moves across the cut towards the end node, back across the cut towards the start node, and then back again towards the end node. In that case, the net flow is 1 but the capacity across the cut moving back and forth is 3.)
All that remains is to show that the maximal flow does not cross back and forth over the cut. Suppose a link crosses back toward the start node. In that case, the end node of the link is in the set A that is reachable from the start node in the residual network. But this link has flow across it so the implicitly defined reverse link has a residual capacity greater than 0. That means you can reach the link's start node in the residual graph. But if both the link's nodes are reachable from the start node, then they are both in set A and the link does not cross the cut. That contradicts our assumption that the link crosses the cut—so no such link can exist.
|Figure 9. Cut Complete: The links that must be cut are drawn in dashed red lines.|
When maximal flow is moving through the network, the net flow across the cut must equal the maximal flow. You just saw that there can be no links moving flow backwards across the cut, so the total flow across the cut must also equal the maximal flow.
If this seems confusing, that's because it is. The technical proof is even more confusing.
Figure 9 shows program NetAlgs displaying a max flow cut for the network shown in Figure 8. The nodes in set A are yellow. The links that were cut are drawn with dashed red lines. I've added a green line by hand (it's not drawn by the program) to separate the nodes in sets A and B.
Notice that if you add up the capacities of the cut links, you get 2 + 0 + 0 + 2 + 0 = 4, which is the network's maximal flow. Also notice that the cut links move only across the cut towards the end node; they never move back towards the start node.
You could modify the program slightly so it doesn't bother removing links with zero capacity, because flow cannot cross them anyway.
Figure 10 shows the same network but with a different destination node—3,3.
|Figure 10. Confusing Cut: The boundary between sets A and B isolates node 3,1 and crosses some links that are not removed by the cut.|
There are two odd things about Figure 10
. First, the cut isolates the node 3
so it is not connected to the other nodes in set B
. In this example, the links that were cut to isolate the node had 0
capacities anyway so the algorithm didn't really need to remove them—but removing them doesn't cost anything.
Second, the green line crosses several links that are not removed by the cut. For example, the 3
link is not removed by the cut but the green line crosses it. Although those links have residual capacities greater than zero, they are situated in positions that are not reachable from the start node in the residual network. In other words, they are directional links that point in the wrong directions, so you can't use them to add extra flow to the network. And because you can't use them to find a path from the start node to the end node, there's no need to remove them.
Next Steps and Getting More Information
This article describes four useful network algorithms: traversal, minimal spanning trees, maximal flow, and minimal flow cut. Traversal and minimal spanning trees are relatively simple. Maximal flow and minimal flow cut are more complicated.
Network algorithms is a heavily studied field, and there are many other interesting algorithms that you can use to perform such tasks as:
- Determining whether two networks are equivalent (it's not as easy as you might think)
- Determining whether you can draw a network without any links crossing
- Determining whether a network is completely connected (whether there is a path between any pair of nodes)
- Finding special structures within networks, such as sets of nodes that are completely connected
For more information on network algorithms, see these other DevX articles: