A equivalent condtion for existence of feasible circulation

Question

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.

Answer 1

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.

Answer 2

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