Suppose you have $m $ sources $s_i$ and $n $ sinks $t_j$, but every source produces a certain type of flow, out of $k $ types, and every sink demands a certain type as well. We would like to know if it is possible to satisfy all demands given the constraints in the network. Assume different flows types all have a certain weight, which is used to compare against edge capacities, and also to check for satisfying the demands.

Is there a formulation of this to a regular max-flow algorithm?

  • 1
    $\begingroup$ Perhaps there is. What have you tried and where did you get stuck? $\endgroup$ – Discrete lizard Feb 24 '18 at 11:59
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Feb 24 '18 at 21:46

This is an instance of multi-commodity network flow. If you insist on integer flows, the problem is NP-hard, but if you allow flows to take fractional values, the problem can be solved in polynomial time using linear programming.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.