Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in the following flow problem, since it turns out to be equivalent to a more general problem.

INPUT: A graph where each edge $e$ has an integer multiplier $q_e$, and a lower bound $b_v$ for each vertex $v$

QUESTION: Is there a flow, such that the flow sent on each $e$ is a multiple of $q_e$ (in either direction), and such that the net flow in to each $v$ is greater than or equal to $b_v$?

Is this problem in P or NP-complete?

So far I have found it is in P if the $q$'s form a chain under division; but if to that we add upper and lower bounds to edges then it becomes NP-complete.

I posted a reformulation using lattices on MO.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.