<p>Consider a cut $C$ in $G^\prime$. Let $c_k(C)$ be its uniform cut capacity in $G$. Then $c_k(C) \geq c_k(s,t)$. By definition of $c_k(C)$, exactly $k$ packets, each of size $c_k(C)/k$ can be packed into the cut $C$. So sum of $\lfloor ku_e /c_k(C) \rfloor$ over the cut is at least $k$. As $c_k(C) \geq c_k(s,t)$, $ku_e /c_k(C) \leq ku_e /c_k(s,t)$. So </p>

<p>$$
\sum_C u_e^\prime = \sum_C \lfloor ku_e /c_k(s,t)\rfloor \geq \sum_C \lfloor ku_e /c_k(C)\rfloor \geq k
$$</p>

CC BY-SA 3.0
2013-03-02T17:27:50.850Z
you are answering my question frequently. thanks a lot for that! If $\sum u'_e< k$ (sum runs over all these edges), you claim $\sum u_e < c_k(s,t)$. But there is a problem: you have $u'_e\le ku_e/c_k(s,t)$ by definition. You would like to have the other direction, i.e. $u'_e\ge ku_e/c_k(s,t)$ to get : $\sum u_e \le \frac{c_k(s,t)}{k }\sum u_e'< c_k(s,t)$ But you just can estimate $u_e$ from below with $u_e'$ and not from above. So why is the latter sum, i.e. $\sum u_e<c_k(s,t)$? Thanks again for your patience.
hulik
CC BY-SA 3.0
2013-03-03T04:18:52.990Z
Yes, that argument was wrong, I missed the floor condition. I have changed the answer now, considering the floor function.
polkjh
CC BY-SA 3.0
2013-03-03T09:18:18.137Z
I am really thankful for your help and patience. But there are still two things which are not completely clear to me: 1. why exactly is the sum of $\left\lfloor ku_e'/c_k(C)\right\rfloor$ over the cut equal $k$? At the end, if we have $\sum_C \left\lfloor ku_e'/c_k(C)\right\rfloor\ge k$ what is the contradiction? Again thank you so much for your help.
hulik
CC BY-SA 3.0
2013-03-03T17:06:11.050Z
Sorry for the clumsiness again, I didn't mean $u_e^\prime$ there. It is supposed to be $k u_e /c_k(C)$. I have edited the answer.
polkjh
CC BY-SA 3.0
2013-03-03T17:11:56.857Z
Thanks for the edit. But again, same problem: why is the sum of $\lfloor ku_e/c_k(C)\rfloor$ over the cut equal $k$ and what is the contradiction at the end
hulik
CC BY-SA 3.0
2013-03-03T17:53:58.367Z
By definition, $c_k(C)$ is the maximum amount that can packed into edges in the cut, using $k$ equal sized packets (so each packet here will be $c_k(C)/k$). If $u_e$ is the capacity of an edge, number of such packets that can be put in that edge is $\lfloor u_e/(c_k(C)/k) \rfloor$. So sum of this over all edges in the cut must be at least $k$ (I had written equality here earlier), as $k$ packets of that size can be placed in the edges.
polkjh
CC BY-SA 3.0
2013-03-03T17:56:39.643Z
Now, $u_e^\prime = \lfloor ku_e/c_k(s,t) \rfloor \geq \lfloor ku_e/c_k(C) \rfloor$, as $c_k(s,t) \leq c_k(C)$. So $\displaystyle \sum_C u_e^\prime = \sum_C \lfloor ku_e/c_k(s,t) \rfloor \geq \sum_C \lfloor ku_e/c_k(C) \rfloor \geq k$. So each cut in $G^\prime$ has size at least $k$. And it is equal to $k$ for the cut corresponding to $c_k(s,t)$. So it will be a min-cut in $G^\prime$.
polkjh
CC BY-SA 3.0
2013-03-04T07:51:31.410Z
thanks again for your patience. Maybe you should delete the first sentence in your answer, since the current proof does not use a contradiction argument.
hulik
CC BY-SA 3.0
2013-03-04T08:40:07.713Z
Yes, that first line was from an older answer, I changed it now. Thanks!
polkjh
CC BY-SA 3.0
2013-03-06T09:52:10.300Z
Sorry for bothering you! I have just a small question: In the proof in the paper, they claim that by integral flow theory there is an integral $s$-$t$-flow of value $k$. Why is this? The Max-Flow-Min-Cut theorem gives a flow with at least flow value $k$. But why exactly $k$? Thank again.
hulik
CC BY-SA 3.0
2013-03-06T12:39:04.877Z
As the capacities are all integral, in the augmenting path, the largest flow we can send is integral. After this, as the current flow is integral and current capacities are integral, new capacities in residual graph are again integral. So we can have an integral flow on augmenting path in this and so on. Repeating this finally results in an integral max flow. More formal proof can be given using induction, but essential idea is the first line above.
polkjh
CC BY-SA 3.0
2013-03-06T18:08:52.350Z
I am very thankful. Maybe my question was not clear, or I do not understand how your comment answer it. For me it is clear that there is a flow (integral). But why has it value $k$(exactly k!). I would agree if we would have at least $k$.
hulik
CC BY-SA 3.0
2013-03-07T04:16:34.120Z
I thought you were looking for why the flow can be integral. I guess the the problem is that we only know min-cut to be 'at least' $k$. So the max-flow might be greater than $k$. But we only want a flow with net flow $k$ (need not be max). We can do this, by following the same process as that of finding max flow. But while sending flows on augmenting paths, we make sure the net flow doesn't exceed $k$. That is, at some point we will have $k-r$ flow already and find an augmenting path that can carry more than $r$ flow through it. In that case we only send $r$ flow in it and stop the algorithm.
polkjh
CC BY-SA 3.0
2013-03-07T07:25:28.997Z
After I asked this question, I also find this solution. But I am very thankful for your help and patience!
hulik
CC BY-SA 3.0
2013-03-02T15:45:35.533Z
2013-03-04T08:38:45.263Z
2013-03-04T08:38:45.263Z
polkjh
<p>I have another question about this <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58.443&amp;rep=rep1&amp;type=pdf" rel="nofollow">paper</a>. There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in this situation on page 9.</p>

<p>If you have a partition $C\cup (V\setminus C)$ with $s\in C$ and $t\in V\setminus C$, the $k$-uniform cut capacity $c_k(C)$ is the maximal volume of a packing of $k$ identically sized packages into the bins with size corresponding to the edges from $C$ to $V\setminus C$. The minimum $k$-uniform $s$-$t$ cut, $c_k(s, t)$, is defined by $c_k(s,t):=\min\{c_k(C)|s\in C\subset V\setminus \{t\}\}$ </p>

<p>My question is then about Theorem 7. How can we derive this lower bound of $k$ for a standard minimum $s$-$t$ cut in the graph $G'$? </p>

<graph-theory><co.combinatorics><multicommodity-flow>
How can we derive this lower bound of a special cut in a graph?
hulik
# How can we derive this lower bound of a special cut in a graph?

(Asked by: username_0 on 2013-03-02)

I have another question about this [paper](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.58.443&rep=rep1&type=pdf). There the authors prove a special version of the maximal flow-minimal cut theorem for uniform exactly-$k$-splittable $s$-$t$-flows. They define the cut in this situation on page 9.

If you have a partition $C\cup (V\setminus C)$ with $s\in C$ and $t\in V\setminus C$, the $k$-uniform cut capacity $c\_k(C)$ is the maximal volume of a packing of $k$ identically sized packages into the bins with size corresponding to the edges from $C$ to $V\setminus C$. The minimum $k$-uniform $s$-$t$ cut, $c\_k(s, t)$, is defined by $c\_k(s,t):=\min\{c\_k(C)|s\in C\subset V\setminus \{t\}\}$

My question is then about Theorem 7. How can we derive this lower bound of $k$ for a standard minimum $s$-$t$ cut in the graph $G'$?

**Tags:** graph-theory, co.combinatorics, multicommodity-flow

---

## 1 answers

### Answer by username_1 on 2013-03-02. Score: 2 | Accepted answer

Consider a cut $C$ in $G^\prime$. Let $c\_k(C)$ be its uniform cut capacity in $G$. Then $c\_k(C) \geq c\_k(s,t)$. By definition of $c\_k(C)$, exactly $k$ packets, each of size $c\_k(C)/k$ can be packed into the cut $C$. So sum of $\lfloor ku\_e /c\_k(C) \rfloor$ over the cut is at least $k$. As $c\_k(C) \geq c\_k(s,t)$, $ku\_e /c\_k(C) \leq ku\_e /c\_k(s,t)$. So

$$
\sum\_C u\_e^\prime = \sum\_C \lfloor ku\_e /c\_k(s,t)\rfloor \geq \sum\_C \lfloor ku\_e /c\_k(C)\rfloor \geq k
$$

> **Comments:**
> **username_0**: you are answering my question frequently. thanks a lot for that! If $\sum u'_e< k$ (sum runs over all these edges), you claim $\sum u_e < c_k(s,t)$. But there is a problem: you have $u'_e\le ku_e/c_k(s,t)$ by definition. You would like to have the other direction, i.e. $u'_e\ge ku_e/c_k(s,t)$ to get : $\sum u_e \le \frac{c_k(s,t)}{k }\sum u_e'< c_k(s,t)$ But you just can estimate $u_e$ from below with $u_e'$ and not from above. So why is the latter sum, i.e. $\sum u_e<c_k(s,t)$? Thanks again for your patience.  
> **username_1**: Yes, that argument was wrong, I missed the floor condition. I have changed the answer now, considering the floor function.  
> **username_0**: I am really thankful for your help and patience. But there are still two things which are not completely clear to me: 1. why exactly is the sum of $\left\lfloor ku_e'/c_k(C)\right\rfloor$ over the cut equal $k$? At the end, if we have $\sum_C \left\lfloor ku_e'/c_k(C)\right\rfloor\ge k$ what is the contradiction? Again thank you so much for your help.  
> **username_1**: Sorry for the clumsiness again, I didn't mean $u_e^\prime$ there. It is supposed to be $k u_e /c_k(C)$. I have edited the answer.  
> **username_0**: Thanks for the edit. But again, same problem: why is the sum of $\lfloor ku_e/c_k(C)\rfloor$ over the cut equal $k$ and what is the contradiction at the end  
> **username_1**: By definition, $c_k(C)$ is the maximum amount that can packed into edges in the cut, using $k$ equal sized packets (so each packet here will be $c_k(C)/k$). If $u_e$ is the capacity of an edge, number of such packets that can be put in that edge is $\lfloor u_e/(c_k(C)/k) \rfloor$. So sum of this over all edges in the cut must be at least $k$ (I had written equality here earlier), as $k$ packets of that size can be placed in the edges.  
> **username_1**: Now, $u_e^\prime = \lfloor ku_e/c_k(s,t) \rfloor \geq \lfloor ku_e/c_k(C) \rfloor$, as $c_k(s,t) \leq c_k(C)$. So $\displaystyle \sum_C u_e^\prime = \sum_C \lfloor ku_e/c_k(s,t) \rfloor \geq \sum_C \lfloor ku_e/c_k(C) \rfloor \geq k$. So each cut in $G^\prime$ has size at least $k$. And it is equal to $k$ for the cut corresponding to $c_k(s,t)$. So it will be a min-cut in $G^\prime$.  
> **username_0**: thanks again for your patience. Maybe you should delete the first sentence in your answer, since the current proof does not use a contradiction argument.  
> **username_1**: Yes, that first line was from an older answer, I changed it now. Thanks!  
> **username_0**: Sorry for bothering you! I have just a small question: In the proof in the paper, they claim that by integral flow theory there is an integral $s$-$t$-flow of value $k$. Why is this? The Max-Flow-Min-Cut theorem gives a flow with at least flow value $k$. But why exactly $k$? Thank again.  
> **username_1**: As the capacities are all integral, in the augmenting path, the largest flow we can send is integral. After this, as the current flow is integral and current capacities are integral, new capacities in residual graph are again integral. So we can have an integral flow on augmenting path in this and so on. Repeating this finally results in an integral max flow. More formal proof can be given using induction, but essential idea is the first line above.  
> **username_0**: I am very thankful. Maybe my question was not clear, or I do not understand how your comment answer it. For me it is clear that there is a flow (integral). But why has it value $k$(exactly k!). I would agree if we would have at least $k$.  
> **username_1**: I thought you were looking for why the flow can be integral. I guess the the problem is that we only know min-cut to be 'at least' $k$. So the max-flow might be greater than $k$. But we only want a flow with net flow $k$ (need not be max). We can do this, by following the same process as that of finding max flow. But while sending flows on augmenting paths, we make sure the net flow doesn't exceed $k$. That is, at some point we will have $k-r$ flow already and find an augmenting path that can carry more than $r$ flow through it. In that case we only send $r$ flow in it and stop the algorithm.  
> **username_0**: After I asked this question, I also find this solution. But I am very thankful for your help and patience!  

---

