# Maximum flow problem with non-zero lower bound

Given $G = (V,E )$ a directed graph, if $X \subseteq V$ we write \begin{align*} \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\ \delta ^{-}(X) &= \delta ^{+}(V - X )\,. \end{align*} $\delta^{+}(v)$ and $\delta^{-}(v)$ are short notation for $\delta^{+}(\{v\})$ and $\delta^{-}(\{v\})$.

We call a circulation in $G$ a function $f\colon E \rightarrow \mathbb{R}$ with the property that $\sum _{e \in \delta ^{+}(v) } f( e ) = \sum _{e \in \delta ^{-}(v) } f( e )$ for any $v \in V$. Let $\ell, u\colon E \rightarrow \mathcal{R}^{+}$ be two functions with the property that $\ell( e ) \leq u( e )$ for any edge $e \in E$. Demonstrate that exactly one of the following statements is true:

• There exists a circulation $f$ in $G$ so that $\ell( e ) \leq f( e ) \leq u( e )$, for all $e \in E$.

• There exists a set $X\subseteq V$ so that $\sum _{e \in \delta ^{+}(X) } u( e ) < \sum _{e \in \delta ^{-}(X) } \ell( e )$.

I tried setting the problem up as an LP problem but I don`t think that is the right way. Any help or idea is well appreciated.

• This problem, known as circulation with demands and lower bounds, is closely related to max flow. See for example these lecture notes: cs.illinois.edu/class/fa07/cs473ug/Lectures/lecture19.pdf. This suggests at least two venues of actions: (1) modify a proof of min cut max flow to this situation, (2) use the reductions among the two problems to translate min cut max flow to your situation. – Yuval Filmus Jan 6 '15 at 11:52