0
$\begingroup$

Cormen's Algorithms 3rd edition Exercise 26.2-13 Page 731:

Suppose that you wish to find, among all minimum cuts in a flow network G with integral capacities, one that contains the smallest number of edges. Show how to modify the capacities of G to create a new flow network $G_0$ in which any minimum cut in $G_0$ is a minimum cut with the smallest number of edges in G.

I don't understand what the author means by the number of edges in a cut. Does he refer to the edges that leave the cut or lie inside of the cut?

In my case, a cut is defined as $C=(S,T)$ where $V=S\cup T$ and $S\cap T = \phi$, a partition on the set of vertices such that source $s\in S$ and sink $t\in T$.

So, by the number of edges in $C=(S,T)$, does the author mean $\sum\limits_{e\text{ out of } S}1\;\;$?

If this is indeed what the author means, then please read the accepted answer to this: post.

Why does the answerer sets $c(e') = n*c(e) + 1$ when setting $c(e') = c(e) + 1$ does the same job?

For example, given $G=(V,E, c)$ graph with capacity constraints $c$, we want to determine a minimum cut with smallest number of edges.

Then, I transform $G=(V,E,c)$ to $G'=(V,E,c')$ where I set $c'(e) = c(e) + 1 \;\;\forall e\in E$.

Now, any max flow algorithm on $G'$ will minimize $\sum\limits_{e\text{ out of }S \text{ of a }(S,T) \text{ cut }} c'(e) \\=\sum\limits_{e\text{ out of }S \text{ of a }(S,T) \text{ cut }} (c(e) + 1) \\= \sum\limits_{e\text{ out of }S \text{ of a }(S,T) \text{ cut }} c(e) + \text{number of edges leaving } S \\= \text{size of }(S,T) \text{ cut in } G + \text{number of edges leaving } S$

$\endgroup$
2
  • $\begingroup$ The cut is the edges that go from $S$ to $T$, that is, leaving $S$. They want you to find a minimum cut with as few edges as possible. $\endgroup$
    – Pål GD
    Commented Dec 9, 2021 at 14:09
  • $\begingroup$ @PålGD Thank you for clarifying that, and yes it does. $\endgroup$
    – chesslad
    Commented Dec 9, 2021 at 14:22

0

Browse other questions tagged or ask your own question.