3
$\begingroup$

I have another question about this paper. 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'$?

|cite|improve this question
$\endgroup$
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – hulik Mar 2 '13 at 17:27
  • $\begingroup$ Yes, that argument was wrong, I missed the floor condition. I have changed the answer now, considering the floor function. $\endgroup$ – polkjh Mar 3 '13 at 4:18
  • $\begingroup$ 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. $\endgroup$ – hulik Mar 3 '13 at 9:18
  • $\begingroup$ 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. $\endgroup$ – polkjh Mar 3 '13 at 17:06
  • 1
    $\begingroup$ 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. $\endgroup$ – polkjh Mar 7 '13 at 4:16

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.