Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such a way that no edge carries both red and blue flow. Is there an efficient way to determine if an assignment of $k_r$ red and and $k_b$ blue flow exists? If so, can it be extended to multiple "colors"?

An extremely naive solution would be to take every subset of edges $E'$ and check whether or not you can send $k_r$ flow through $G[E']$ and $k_b$ flow through $G[E\setminus E']$.

I was looking at this question of assigning people to rooms with constraints and thought that if you could solve the above edge disjoint flow problem, you could solve the linked question as well (it wouldn’t be faster than the claimed $O(n^3)$ time algorithm, though).

  • $\begingroup$ I would look for a reduction from some NP-complete problem (maybe 1-in-3 3SAT?). Can you think of a gadget that will ensure that two edges have opposite-colored flows through them (they don't both have flows of the same color)? $\endgroup$ – D.W. Mar 21 '20 at 18:14

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.