1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 6 '15 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.