I have previously written about flows in these blogs: 1, 2, 3.
Minimum cuts are a very fascinating topic for me. There are a lot of maximum flow problems where there's a fairly simple chain of reductions leading to "you should use flow", but there are also a lot of flow problems where flow comes apparently out of nowhere. Particularly fascinating are those where it's more convenient to think in terms of minimum cut: they work, because minimum cut allows you to model partitioning a set in two, with some additional implication-like constraints. Here are a couple of problems with that nature:
- ARC085E - MUL (this reduction is almost standard these days)
- ARC142E - Pairing Wizards
- 104925D - Filesystem
There are also flow problems on graphs with special shapes where thinking in terms of cuts makes the flow easy to efficiently calculate.
Anyway, let's move on to the actual topic of the blog. I recently had a couple discussions on various Discord servers about some problems on minimum cuts. The problems were:
- Given a flow network where all minimum cuts have a nonempty intersection, prove that there exists an edge that is in every minimum cut.
- Given a flow network where each edge has a label (independent of capacity), calculate the lexicographically smallest minimum cut, in time $$$O(n^2 m)$$$.
Both problems involve statements like "among all minimum cuts". I thought the problems were very interesting, and shared a common thread, so I decided to write them up in a blog. They also lead neatly into some discussion of more general and abstract theory.