4
$\begingroup$

A circulation in a directed graph $D$ is a function $g:E(D)\rightarrow\mathbb{R}$ satisfying the conservation condition at every vertex. Let $l,u:E(D)\rightarrow \mathbb{R}^{+}_{0}$ be a lower and upper capacity function, resp. And assume for each edge $e$, $l(e)\le u(e)$.

A circulation $g$ is feasible if $l(e)\le g(e) \le u(e)$ for every edge $e$.

Prove that there exists a feasible circulation iff $l^+(A)\le u^-(A)$ for every set $A\subset V(D)$.

Hint: Add a vertex $s$ and an edge from $s$ to every vertex of $D$, and a vertex $t$ and an edge from every vertex of $D$ to $t$. Define $c(sv)=l^-(v), c(vt)=l^+(v), c(e)=u(e)-l(e)$ for $v \in V(D)$ and $e \in E(D)$. Given a flow f of value $\Sigma_{e\in E(D)} l(e)$ in the network thus defined, consider $f+l$.

I proved the forward direction. In the backward direction, if there exists such a flow $f$, then $f+l$ is in the lower and upper capacity bound. But I can't prove such a flow $f$ exist. I want to use max-flow min-cut theorem, but I can't find a minimal cut. Because I don't know the relation between $u(e)-l(e)$ and $l^+(x)+l^+(y)$ where $e=xy$.

And even if such flow $f$ exists, I'm confused to find out $f+l$ is a circulation and where the condition "$l^+(A)\le u^-(A)$ for every set $A\subset V(D)$" is used.

$\endgroup$
  • $\begingroup$ What is the "conservation condition"? What are "lower and upper capacity functions"? What are $l^{+}$ and $u^{-}$? $\endgroup$ – Mike Pierce Sep 19 '15 at 18:16
  • $\begingroup$ $l^+(X)=\sum_{e=(x,y)\in E(D), x\in V(D)-X, y\in X}l(e)$, $u^-(X)=\sum_{e=(x,y)\in E(D), x\in X, y\in V(D)-X}u(e)$. “Lower and upper capacity functions" means a flow on each edge is in the range of $[l(e),u(e)]$. "Conservation condition" means $g^+(v)=g^-(v), v\in V(D)$. $\endgroup$ – Connor Sep 19 '15 at 20:09
0
$\begingroup$

For any edge $e = (v, w)$, denote $l(v, w) = l(e)$ and $u(v, w) = u(e)$. Let $E$ be the set of edges and $V$ be the set of nodes in our problem.

Let's name your problem as $\Pi$, the circulation problem with lower bound and upper bound on the amount of flow in each edge. We will show that it is equivalent to another problem $\Sigma$, which is a multi-source multi-sink network flow problem, and each edge having an upper bound on the amount of flow that can flow in it, but having NO lower bound.

Intuitively, for each edge $(v, w)$ in $\Pi$, we will push $l(v, w)$ amount of flow on this edge. By the circulation problem property, it means that there must be an intake of $l(v, w)$ flow in $v$, and there is an excess of $l(v, w)$ flow in $w$ that must go somewhere.

To formalize this idea, we translate $\Pi$ into $\Sigma$ as follows. $\Sigma$ has the same set of nodes with $\Pi$. For each edge $(v, w)$ in $\Pi$, we create an edge $(v, w)$ in $\Sigma$ whose capacity $g(v, w)$ is $u(v, w) - l(v, w)$ (this number will be non-negative, since $l(v, w) \le u(v, w)$.

In addition, we increase the amount of initial flow in $w$ by $l(v, w)$, and decrease the amount of initial flow in $v$ by $l(v, w)$. More formally, let the total amount of initial flow in any node $v$ be denoted by $f(v)$. We have that $f(w) = \sum_{(v, w) \in E} l(v, w) - \sum_{(w, v) \in E} l(w, v)$. If $f(v)$ is positive, we treat $v$ as one of the source nodes with initial flow equal to $f(v)$. Otherwise, we treat $v$ as one of the sink nodes who expects to receive $-f(v)$ flow.

It is clear that there is a one to one correspondence between solutions in $\Pi$ and $\Sigma$, since between every two such solutions, we have that $g'(v, w) = g(v, w) - l(v, w)$. Since $0 \le g'(v, w) \le u(v, w) - l(v, w)$, we must have $le(v, w) \le g(v, w) \le u(v, w)$, and vice versa.

Finally, we need to show that if the $l(W) \le u(\bar{W})$ for every set $W \subseteq V$ condition holds, then $\Sigma$ has a flow. To do this, we use the min cut max flow theorem on $\Sigma$. For convenience, we convert $\Sigma$ into its corresponding single source single sink version $\Sigma'$, which is performed by the steps outlined in the hints, namely by adding two nodes $s$ and $t$ into $\Sigma'$ to act as the source and the sink. For every source node $v \in \Sigma$, we add an edge $(s, v)$ with capacity $f(v)$ in $\Sigma'$. Similarly, for every sink node $v \in \Sigma$, we add an edge $(v, t)$ with capacity $-f(v)$ in $\Sigma'$. The total amount of flow that needs to flow in this graph by $\sum_{v | f(v) > 0} f(v)$. This is a well known reduction from multi source multi sink network flow problem to single sink single source network flow problem.

Thus, we only need to show that for every cut separating $s$ and $t$ in $\Sigma'$, the cut is at least $\sum_{v | f(v) > 0} f(v)$. Consider any cut of the nodes in $\Sigma'$ that separates $s$ and $t$. We can separate all the remaining nodes into four types:

enter image description here

That is:

  • A: set of nodes that are connected to s and in the same partition with s
  • B: set of nodes that are connected to s and in the same partition with t
  • C: set of nodes that are connected to t and in the same partition with s
  • D: set of nodes that are connected to t and in the same partition with t

For convenience, for any set of nodes $X$ and $Y$, we denote by $XY = \sum_{x \in X} \sum_{y \in Y} l(x, y)$. Also, when $X$ is a set of nodes, we let $f(X)$ to be $\sum_{x \in X} f(x)$.

The cut is then at least...

\begin{eqnarray*} \text{cut} &=& f(B) - f(C) + \sum_{x \in A \cup C} \sum_{y \in B \cup D} u(x, y) - l(x, y) \\ &=& f(B) + CA + CB + CD - AC - BC - DC + \sum_{x \in A \cup C} \sum_{y \in B \cup D} u(x, y) - \sum_{x \in A \cup C} \sum_{y \in B \cup D} l(x, y) \\ &\ge& f(B) + CA + CB + CD - AC - BC - DC + \sum_{x \in B \cup D} \sum_{y \in A \cup C} l(x, y) - \sum_{x \in A \cup C} \sum_{y \in B \cup D} l(x, y) \\ &=& f(B) + CA + CB + CD - AC - BC - DC + BA + BC + DA + DC - AB - AD - CB - CD \\ &=& f(B) + BA + DA + CA - AB - AD - AC \\ &=& f(B) + f(A) = \sum_{v | f(v) > 0} f(v) \end{eqnarray*}

The third line is by the precondition that $l(W) \le u(\bar{W})$ for every set $W \subseteq V$ condition.

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