2
$\begingroup$

I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph.

Firstly, let's state (for completeness) that an s-t cut is the partitioning of the vertices in the graph, into two parts, such that the source s is in one partition and the sink t is in the other. The cut-set is the set of edges that are going from vertices in the partition that contains s to those in the other partition.

There may be multiple s-t cuts that have the same capacity as the min-cut (with different sized cut sets). The problem that I wish to solve is, how to find the minimum s-t cut that also has the minimum size cut set?

For example, in the following graph where s = 0 and t = 4:

enter image description here

We can clearly see that the capacity of the minimum cut is 2. One possible way to get this is to take edges 0-2 and 1-3 (This cut set has size 2). Another possible way to do this is to take edge 3-4 instead (This cut set has size 1) which is the optimal answer.

I have researched about this question and some people are saying that we need to transform the edge capacity, C, of every edge to C * (|E| + 1) - 1, where |E| is the number of edges in the graph.

One such discussion here: https://codeforces.com/blog/entry/51748
Another such discussion here: https://stackoverflow.com/questions/38408852/finding-the-lowest-amount-of-edges-in-all-minimum-cuts-in-flow-network

The problem is, I don't understand why this formula works. In particular, why do we need to multiply by (|E| + 1) and not some other number? I cannot see how multiplying by any other number would "change" the augmenting paths in the graph as stated in the cited links.

Could someone please advise me?

Edit: The offset in the formula should be +1 and not -1 in order to get the cut-set of the smallest size.

$\endgroup$
4
$\begingroup$

Those answers assume that all edge capacities are integers. Assuming they are, this works.

Suppose the min-cut in the original graph has total capacity $x$; then it will have total capacity $x(|E|+1)+k$ in the transformed graph, where $k$ counts the number of edges crossing that cut. Note that if you consider any cut in the original graph with larger capacity, its original capacity will be $x+1$ or more, so its total capacity in the transformed graph will be $(x+1)(|E|+1)+k'$ for some $k'$ in the range $0 \le k' \le |E|$. Now

$$\begin{align*} (x+1)(|E|+1)+k' &= x(|E|+1)+|E|+1+k'\\ &> x(|E|+1)+|E|\\ &\ge x(|E|+1)+k, \end{align*}$$

so any cut in the original graph that isn't a min-cut won't be a min-cut in the transformed graph, either.

In other words, any min-cut of the transformed graph will be a min-cut of the original graph.

Moreover, out of all of the min-cuts in the original graph, the one whose cut set is smallest is the one that will have lowest capacity in the transformed graph (since the transformation adds one for each edge in the cut set). So, the min-cut in the tranformed graph will be a min-cut in the original graph, and it will break ties by choosing the one with smaller cut set.

$\endgroup$
  • $\begingroup$ I think there is an error in your working. (x+1)(|E|+1)-k' should be x(|E|+1)+|E|+1-k' $\endgroup$ – LanceHAOH Sep 28 at 1:12
  • $\begingroup$ Also, I just realised that the correct offset is +k not -k. Because if we use -k, the cut set (of any min-cut) that is smallest in the original graph should be the one with highest capacity in the transformed graph because its k is the smallest. But if we use +k, then the smallest cut set (of any min-cut) in the original graph would indeed be the one with smallest capacity in the transformed graph. $\endgroup$ – LanceHAOH Sep 28 at 1:50
  • $\begingroup$ @LanceHAOH, oops, you're right. Sorry about that. See revised answer for a correction; hopefully the reasoning is now correct. $\endgroup$ – D.W. Sep 28 at 4:51
  • $\begingroup$ Almost. This statement needs updating as well: "(since the transformation subtracts one for each edge in the cut set)". Since the offset is +k, the transformation adds one for each edge in the cut set. $\endgroup$ – LanceHAOH Sep 28 at 5:41
  • $\begingroup$ @LanceHAOH, thanks! Fixed. $\endgroup$ – D.W. Sep 28 at 16:18

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.