3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.