# A equivalent condtion for existence of feasible circulation

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.

• What is the "conservation condition"? What are "lower and upper capacity functions"? What are $l^{+}$ and $u^{-}$? – Mike Pierce Sep 19 '15 at 18:16
• $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)$. – Connor Sep 19 '15 at 20:09

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:

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.