*This is an experimental rewrite of a [post](https://codeforces.net/blog/entry/128552) by [user:-is-this-fft-,2024-09-18]. I consider this post more intuitive and readable than the original, but [user:-is-this-fft-,2024-09-18] 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 that 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](https://codeforces.net/blog/entry/128552) 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:↵
↵
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 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.↵
↵
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. 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$.↵
↵
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$ 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.
↵
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 that 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](https://codeforces.net/blog/entry/128552) 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:↵
↵
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 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.↵
↵
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. 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$.↵
↵
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$ 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.
