Using residual graphs to analyze properties among minimum cuts
Difference between en6 and en7, changed 0 character(s)
*This is an experimental rewrite of a [post](https://codeforces.me/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.me/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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English purplesyringa 2024-09-18 18:14:24 4 Tiny change: 'ust share that edge.\n- ' -> 'ust share an edge.\n- '
en8 English purplesyringa 2024-09-18 18:02:00 357
en7 English purplesyringa 2024-09-18 17:40:51 0 (published)
en6 English purplesyringa 2024-09-18 17:39:42 57
en5 English purplesyringa 2024-09-18 16:16:21 3 Tiny change: 'was the only who resea' -> 'was the one who resea'
en4 English purplesyringa 2024-09-18 04:30:59 274
en3 English purplesyringa 2024-09-18 02:24:40 55
en2 English purplesyringa 2024-09-18 02:11:55 6 Tiny change: 'what I did?), but so' -> 'what I did there?), but so'
en1 English purplesyringa 2024-09-18 02:11:32 5155 Initial revision (saved to drafts)