# Smallest $s$-component in mincut

Suppose there is a directed graph $$G=(V,E)$$, with source $$s$$ and sink $$t$$, and I compute the max flow on it. Then I know that I can find a min-cut $$(A,B)$$, by letting $$A$$ be the set of vertices that are reachable from the source $$s$$.

My question is is this set $$A$$ the smallest possible $$s$$-component? I think it is. To be precise, does there exist a subset of vertices $$A^*$$, such that $$(A^*, V\setminus A^*)$$ is a min-cut, and for all other possible subsets of vertices $$A$$ such that $$(A, V\setminus A)$$ is a min-cut, we have $$size(A^*) \leq size(A)$$.

Furthermore, for any other min-cut $$(C,D)$$, do we have $$A \subset C$$?. I also think this is the case. But I can't prove it.

Any intuition / hints are much appreciated!

Edit

Definition of $$s$$-component: The min-cut is the partition of the vertices of $$G$$ into two disjoint sets $$(A,B)$$, where $$A$$ contains the source $$s$$ and $$B$$ contains the sink $$t$$. The $$s$$-component w.r.t. a min-cut is then the set $$A$$.

By "smallest" $$s$$-component I mean $$s$$-component with smallest cardinality. I'm wondering if there can be several different minimal $$s$$-component w.r.t. set inclusion, i.e. $$s$$-components with same cardinality, but are not equal as sets. Equivalently, wondering if there is a minimum $$s$$-component; a set of vertices that is in ALL $$s$$-components.

I believe that the answer is yes: any min-cut constructed in this way from a max-flow will also have minimum possible cardinality, among all possible min-cuts.

There can be multiple min-cuts, all with the same cost. They form a lattice structure: the intersection of two min-cuts is another min-cut, and the union of two min-cuts is another min-cut. You can identify a "smallest" element in this lattice by taking the intersection of all min-cuts; this will be another min-cut, and it will have the smallest cardinality of all min-cuts.

As I understand it, it is possible to prove that the min-cut obtained from a max-flow is always this "smallest" min-cut. Or, to put it another way, if you think of the source $$s$$ on the left and the sink $$t$$ on the right, then any min-cut obtained from a $$s,t$$-max-flow will be always be a "leftmost" cut. Also, it will follow that any other min-cut will be a superset of this cut found by max-flow, exactly as you conjectured.

For references to these results, and other related material, see the following questions (note: you may need to double-check some of the claims yourself, as I have not personally verified them):

Does Ford-Fulkerson always produce the left-most min-cut

https://stackoverflow.com/a/8101250/781723

https://stackoverflow.com/q/26696312/781723

https://stackoverflow.com/q/9210755/781723

https://stackoverflow.com/q/41964288/781723

Answer yo your first question: Not necessarily. Any off-the-shelf max-flow or min-cut algorithm will produce an arbitrary min-cut partition, not a minimum cardinality one. But you can augment your graph, such that the max-flow output is what you want:

Let $$A, V\setminus A$$ and $$B, V\setminus B$$ be min-cut partitions: $$\delta(A,V\setminus A)=\delta(B,V\setminus B) = \min_{X\subseteq V,s\in X} \delta(X,V\setminus X)$$ Now, add edges with weight $$\varepsilon>0$$ from vertex $$t$$ to all other vertices. The new cuts corresponding to $$A$$ and $$B$$ have the updated weights: $$\delta(A, V\setminus A) + |A|\cdot \varepsilon, \\ \delta(B, V\setminus B) + |B|\cdot \varepsilon$$ respectively. Since both the first terms are equal, the second terms $$\varepsilon |A|$$ and $$\varepsilon |B|$$ will determine the order. So the min-cut in the new graph is the minimum cardinality, min-cut partition in the original graph. The only caveat is that $$\varepsilon$$ must be chosen small enough, to make sure it the min-cut in the new graph is a min-cut in the original graph. If weights are integers, any value less than $$1/|V|$$ would suffice.

($$\star)$$ : $$\delta(X,V\setminus X)$$ denotes the sum of weights of cross-edges between $$X$$ and $$V\setminus X$$.