# 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^{-}$? Sep 19, 2015 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)$. Sep 19, 2015 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.

Here is a slightly shorter solution using a different notation. We consider a directed graph $$G = (V, E)$$ with edge capacities given by $$c\colon E \to \mathbb{R}^+$$ and node demands given by $$d\colon V \to \mathbb{R}$$. A circulation is an assignment $$f\colon E \to \mathbb{R}^+$$ satisfying $$c(e) \leq f(e)$$ for all edges $$e$$ and $$\sum_{e \text{ into } v} f(e) - \sum_{e \text { out of } v} f(e) = d(v)$$ for all vertices $$v$$.

The forward direction — if there exists a circulation, then $$\sum_{v \in V} d(v) = 0$$ and for any partition $$(A, B)$$ of $$V$$, $$\sum_{v_B} d(v) \leq \operatorname{cap}(A, B)$$ — is quite direct. You just need to use the definition of a circulation and think about what edges cancel in the sums.

For the backward direction, we consider the contrapositive. Suppose that there does not exist a circulation in $$G$$, and that $$\sum_{v \in V} d(v) = 0$$. Let us convert the circulation network into a flow network $$G'$$ by adding a source $$s$$ and a sink $$t$$, and add edges $$(s, v)$$ of capacity $$d(v)$$ where $$d(v) > 0$$, and edges $$(v, t)$$ of capacity $$-d(v)$$ where $$d(v) < 0$$. Running the Ford-Fulkerson algorithm on $$G'$$ should give us $$\operatorname{max-flow}(G') = \operatorname{cap}(A, B) < \sum_{\substack{v \in V \\ d(v) > 0}} d(v)$$ (for otherwise the max-flow gives a circulation).

But $$A = \{s\} \cup A'$$ and $$B = \{t\} \cup B'$$ with $$A', B' \subseteq V$$, and \begin{aligned} \operatorname{cap}(A, B) &= \operatorname{cap}(A', B') + \sum c(s \to B) + \sum c(A \to t) \\ &= \operatorname{cap}(A', B') - \sum_{\substack{v \in B \\ d(v) < 0}} d(v) + \sum_{\substack{v \in A \\ d(v) > 0}} d(v) \end{aligned} Now $$\operatorname{cap}(A, B) < \sum_{\substack{v \in V \\ d(v) > 0}} d(v) = \sum_{\substack{v \in B \\ d(v) > 0}} d(v) + \sum_{\substack{v \in A \\ d(v) > 0}} d(v)$$ so $$\operatorname{cap}(A', B') < \sum_{\substack{v \in B \\ d(v) < 0}} d(v) + \sum_{\substack{v \in B \\ d(v) > 0}} d(v) = \sum_{v \in B} d(v)$$ where $$(A', B')$$ is a partition of $$V$$.