Smallest $s$-component in mincut

Question

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.

Answer 1

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 2

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