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 only 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:

• Finding the lexicographically smallest minimum cut in terms of the edges that cross it.
• Proving that in a flow network where every pair of minimum cuts shares a common crossing edge, all minimum cuts must share that edge.

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. We’ll start with the second one, as it provides a good illustration of the technique.

Problem 2: 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:

1. Put all vertices $$$v$$$ such that $$$s \leadsto v$$$ in $$$G_f$$$ to the $$$S$$$ side, and the rest to the $$$T$$$ side.
2. 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:

1. 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.
2. Likewise, $$$u$$$ is in the $$$T$$$ side of every minimum cut.

Thus, $$$v \to u$$$ crosses every minimum cut. Problem solved.

Problem 1: 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.

We can solve this in four steps:

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

2. Disable 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$$$.

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

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

   We'll build the lexicographically smallest minimum cut incrementally by adding edges in lexicographical order, as long as they don't violate the conditions.

   • 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$$$, 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.