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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.