This is an experimental rewrite of a post by -is-this-fft-. I consider this post more intuitive and readable than the original, but -is-this-fft- was the one who researched this topic.
Minimum cuts in flow networks are quite fascinating. We often see flow-related problems where the solution is clear-cut (see what I did there?), but sometimes the idea of flow seems to appear unexpectedly. In some cases, thinking in terms of minimum cuts is more intuitive than flow itself.
Let’s explore two interesting problems about minimum cuts:
- Proving that in a flow network where every pair of minimum cuts shares a common crossing edge, all minimum cuts must share an edge.
- Finding the lexicographically smallest minimum cut in terms of the edges that cross it.
For simplicity, we'll assume all edges have unit capacities. This doesn't affect the generality of our solutions since edges with higher capacities can be split into multiple unit-capacity edges.
Key insight
It is well-known that the maximum flow and the minimum cut of a network have equal numerical values. But there’s more to this relationship:
Characteristic property. For any maximum flow $$$f$$$, an $$$s-t$$$ cut is minimal if and only if no edges in the residual graph $$$G_f$$$ cross it.
Proof. Every $$$s-t$$$ cut crosses $$$f$$$ by weight $$$F$$$ (the value of the flow). A cut is minimal when it crosses $$$G$$$ by weight $$$F$$$. Since $$$G = G_f + f$$$, this means the cut crosses $$$G_f$$$ by weight $$$0$$$. As $$$G_f$$$ has no negative edges, the cut must not cross any edges.
The original post provides an alternative proof based on the linear programming theory.
Now, let’s leverage this property to tackle our two problems.
Problem 1: Shared crossing edges in minimum cuts
Problem. In a flow network where any two minimum cuts have a common crossing edge, prove that all minimum cuts share a crossing edge.
First, take any maximum flow $$$f$$$ and examine its residual graph $$$G_f$$$. This gives us two (possibly identical) minimum cuts straight away:
- Put all vertices $$$v$$$ such that $$$s \leadsto v$$$ in $$$G_f$$$ to the $$$S$$$ side, and the rest to the $$$T$$$ side.
- Put all vertices $$$u$$$ such that $$$u \leadsto t$$$ in $$$G_f$$$ to the $$$T$$$ side, and the rest to the $$$S$$$ side.
By the problem's assumption, these two cuts are both crossed by some edge $$$v \to u$$$. Then:
- By the choice of cuts, $$$s \leadsto v$$$ in $$$G_f$$$. By the characteristic property, this path doesn't cross any minimim $$$s-t$$$ cut, so $$$v$$$ is in the $$$S$$$ side of every minimim cut.
- Likewise, $$$u$$$ is in the $$$T$$$ side of every minimum cut.
Thus, $$$v \to u$$$ crosses every minimum cut. Problem solved.
Problem 2: Edge-wise lexicographically smallest minimum cut
Problem. Given a flow network with labeled edges, find the lexicographically smallest minimum cut. The cuts are compared by the ordered lists of crossing edges.
The basic idea is to incrementally build the answer, tracking information known about the cut, and adding edges in lexicographical order as long as they don't violate any conditions. Here's how to do that in four steps:
Find any maximum flow $$$f$$$ and construct the residual graph $$$G_f$$$. The time complexity of this step will dominate the overall algorithm. For Dinitz's algorithm, this takes $$$O(n^2 m)$$$.
Prepare for enumeration by disabling edges $$$v \to u \in G$$$ such that a $$$v \leadsto u$$$ path exists in $$$G_f$$$. Such edges can never cross a minimum cut by the characteristic property. To identify such edges:
- Check if a direct edge $$$v \to u$$$ exists in $$$G_f$$$.
- If not, then naturally $$$u \to v$$$ must be in $$$G_f$$$. Under this condition, checking $$$v \leadsto u$$$ is equivalent to checking that $$$v$$$ and $$$u$$$ belong to one strongly connected component of $$$G_f$$$.
An $$$s-t$$$ cut is any assignment of $$$S$$$ and $$$T$$$ to vertices such that $$$s$$$ is $$$S$$$ and $$$t$$$ is $$$T$$$. Due to the characteristic property, a minimum cut is also subject to these inference rules:
- If $$$v$$$ is $$$S$$$ and $$$v \to u$$$ is in $$$G_f$$$, then $$$u$$$ is also $$$S$$$,
- If $$$u$$$ is $$$T$$$ and $$$v \to u$$$ is in $$$G_f$$$, then $$$v$$$ is also $$$T$$$.
Use DFS to mark each vertex as belonging to $$$S$$$, $$$T$$$, or unknown.
It's easy to see that as long as there are no contradictions, any single unknown vertex can be forced to $$$S$$$ or $$$T$$$ (followed by inference) without introducing contradictions.
- Before adding an edge $$$v \to u$$$, check that it's enabled, $$$v$$$ is $$$S$$$ or unknown, and $$$u$$$ is $$$T$$$ or unknown. If these conditions hold, the edge is safe to add.
- Mark $$$v$$$ as $$$S$$$ and propagate this by marking everything reachable from $$$v$$$ as $$$S$$$ too.
- Since $$$v \not\leadsto u$$$ holds for enabled edges, we can now safely mark $$$u$$$ as $$$T$$$ and propagate again.
Continue this process until all edges have been processed. Once the edges are exhausted, any remaining unknown vertices can be marked $$$S$$$ to produce a final cut. As no vertex is marked more than once, this step takes $$$O(n + m)$$$ time.
-is-this-fft- and me thought it's a good idea to share our exchange about the rewrite to compare our approaches to writing. I think there's some good universal ideas here that might be a good learning opportunity. Some others are just preferences, and I might be wrong about things, so follow your intuition and don't let some flaws or "flaws" in your posts dissuade you from writing.
purplesyringa: I removed something people are already expected to know from the introduction, like basic definitions. Given the level of knowledge you expect from the readers, rehashing that will likely annoy them more than help them get up to speed.
-is-this-fft-: Maybe. I usually wouldn't rehash definitions so much, but I feel the need to do this with flows because there are kinda multiple formalizations and people might get them mixed up?
purplesyringa: I also removed references to earlier unrelated problems. They would fit great in a post introducing minimum cuts, but the gap between someone who doesn't know the applications of mincut and your target audience is quite high. Maybe write something more introductory if you have time?
purplesyringa: I swapped the two problems, as the first one sounds more useful and practical, so it's more likely to catch the eye of a person who just skims through the content to see if they want to read it.
-is-this-fft-: Right now you have swapped the indices, but not the order. My choice to put the shared-crossing edge problem first was deliberate: the solution to this problem is much shorter. It's a more direct application of the key point; in the second problem its somewhat distracted by other details.
I see your point that it's "more practical" (competitive programmers don't care about problems that are just proofs, lol). But it's also good practice to start from the simplest problem that can be solved by your technique.
purplesyringa: This is why I showed the solution of the simpler problem first. I admit I'm iffy about unaligned indices too, so I'll probably swap them back.
purplesyringa: I focused on the insight in the relationship between maximum flow and minimum cut instead of mentioning it offhandedly. In your post, it's the last observation of the three, so it's likely to get less attention than the other two.
purplesyringa: I made the statement of the property more accessible and intuitive instead of using set-theoretical notation. Cuts are inherently symmetric, and interpreting them as a single set instead of a disjunctive union hides that symmetry and makes the logic seem twice as complex.
purplesyringa: I rewrote the proof. I don't use a proof that relies on the details of another proof that experts are likely to skip on first read, because they already know how to prove the 2nd observation. Instead, I assume the equality "mincut=maxflow" is already known and prove the result in a straightforward manner.
purplesyringa: I integrated the sentence "This observation gives us a nice characterization of the set of all minimum cuts..." into the applications to immediately demonstrate its usefulness.
purplesyringa: In the solution to the first problem, you show the shared property first and the two particular cuts second. However, you reference the two cuts first and apply the characteristic property second. So I swapped them.
purplesyringa: I used notation like $$$\leadsto$$$ instead of words like "reachable". This helps retain the symmetry (compare to "vertex reachable from s/vertex from which t is reachable" to $$$s \leadsto v$$$/$$$u \leadsto t$$$). In addition, the arrow matches our graph intuition, so you don't even have to know the meaning of $$$\leadsto$$$ prior to reading the article.
purplesyringa: I replaced proofs by contradiction. These tend to introduce unnecessary complexity. Instead of saying "If X, then Y, then Z, which contradicts the statement. If not X, ...", say "By assumption, !Z. Hence !Y, so !X. ...". Very often, proofs by contradiction arise in first drafts, but it's very useful to take a step back and rewrite the proofs to avoid contradiction before publishing the article.
purplesyringa: I removed the time complexity of the solution to the first problem from the statement to demonstrate that it depends on the chosen maxflow algorithm and isn't the best possible bound.
-is-this-fft-: True, time complexity is not the main point of the statement. I wanted to make it clear that I expect only one call to a maximum-flow solving black box (instead of trying to remove every edge and solving maximum flow O(m) times or similar).
purplesyringa: Interesting. Personally, I think that any solution involving trying to remove every edge is already quite complicated, so few people are going to think about it before reading your better solution. But maybe that's just my CP level speaking.
purplesyringa: The way you hid the final solution to this problem under a spoiler feels like cheating. It's like saying "I'm running out of time and the solution is complicated, so let's sweep it under the rug". So it must stay and be the focus.
Worse, the final solution is not an extension of the worse one, but a significant modification. The way it reads is "here's what we're going to use, oh, wait, no, let's do this instead, but only if you're smart". It feels like a waste of time to both experts and beginners. I simplified the final solution, sprinkling ideas that beginners could apply to get stupid-but-good-enough solutions in other situations, and removed everything else.
-is-this-fft-: I understand the point. But here was my reasoning: the final algorithm should already be clear from the earlier version and the paragraph explaining how to get rid of rollbacks. The earlier algorithm needs pseudocode because it's hard to explain the propagation otherwise. The change we made to get rid of rollbacks doesn't. The final pseudocode exists only "for completeness", but shouldn't be needed to understand the algorithm.
purplesyringa: "the final algorithm should already be clear from the earlier version and the paragraph explaining how to get rid of rollbacks": Yes, it's quite clear. But I think it's important not to repeat yourself and to use either prose or pseudocode, not both.
"The earlier algorithm needs pseudocode because it's hard to explain the propagation otherwise": Personally, it doesn't seem that way to me. "If u is marked and u->v, v is marked" screams "propagate it with DFS" to me, and I think focusing so much on it is unnecessary. We are people, switching focus is hard for us, and going from text to code/pseudocode and back is non-trivial.
purplesyringa: While bullet-point pseudocode is quite useful, it's not code, so it can be made more readable. I used S/T labels instead of 1/0.
purplesyringa: I made the derivation seem linear. Instead of saying "here's how to rewrite the statement to hopefully bring us closer to the solution", which doesn't really give a sense of progression, I derived the solution step-by-step, with each step clearly extending the information known about the min-cut. The 1st step introduces the link between the min-cut and the max-flow, the 2nd step proves it doesn't contain some edges, the 3rd step proves some vertices belong to S or T, and the 4th step finally produces the result.
purplesyringa: I don't assume the readers are idiots, so to speak. Saying "We can check this with DFS", followed by "propagate with DFS", followed by "If implemented carefully, this takes linear time" brings attention to unimportant parts, so I just say "Use DFS to...", because the target audience knows how to apply it.
purplesyringa: "Do A. This lets us do B" reads better than "Let's do B. For that, do A first". The former requires the person to focus on A, then B. The latter makes them focus on B, then A, then think about how A helps with B. That's one more step than necessary. Saying "To do A, do B" is permissible when B is very simple and doesn't require any thinking, but not in the case of the edge validity check, when you introduce SCCs for the first time. To fix this, I made SCC computation a separate step and immediately showed how to disable some edges with it, so that the reader no longer has to think about SCC by the time they reach the 4th step.
purplesyringa: Finally, I removed the section on complementary slackness. It's interesting, but what's the target audience? Learning LP from this post alone is impossible, teaching duality to newcomers is hopeless, people who know a thing or two about LP will check Wikipedia or another source instead of using your lists/tables, and experts are probably already familiar with the result. I don't think it's totally useless, but I know I can't improve it, so I just inserted the reference to the LP proof next to my simpler proof.
-is-this-fft-: It's the final section of the blog. I want to show that "this is not the end of the story, this is a specific case of a larger phenomenon". "Max flow = min cut" is a specific case of strong duality, working with residual graphs is a specific case of complementary slackness.
Who is the target audience? Yes, it's people who don't know LP or know a thing or two. But also people who know LP in principle, but don't have a strong intuition on complementary slackness and need to see an example. Learning LP from this is not really intended -- the purpose of this is to show that it exists. Maybe give people inspiration to learn LP.
I guess I went overboard with it and added more than necessary "for completeness". You can see how it happened: "I need to show that this fact is exactly complementary slackness" -> "Ok, then I need to agree on an LP formalization of maximum flow and minimum cut" -> "And probably show that they are duals" -> "Ok, now I need to put the proof of duality under a spoiler and probably reference the rules for dualizing an LP". You can see how it snowballs like that.
purplesyringa: I admit I didn't consider this, huh. Personally, I did find some inspiration to learn some LP theory from your post. Thank you for that!
I find it acceptable to add more difficult content to the very end. There's just one thing you need to track. People often check the length of the post before reading it, and the longer the post, the less likely they are to interact with it, even if the second half wasn't really expected to be read. I think a somewhat shorter description would do wonders.
Auto comment: topic has been updated by purplesyringa (previous revision, new revision, compare).
Being a blue and looking from the outside, I can agree that the shorter blog is definitely more appealing. However, I like the fact the original blog has pictures (or illustrations?), which I personally find more attractive in theoretical blogs. Nice blog in all!
You're right, pictures would work well here. Sadly I didn't have time to recreate them and I think the pictures in the original post would be confusing with all the notation changes. :(
I think you mean all minimum cuts must share an edge?
That's a typo. Thanks for noticing!