It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with demands on acyclic digraphs with maximum outdegree two:INSTANCE: An acyclic directed graph  $G=\left(V,E\right)$ with maximum  outdegree two, a capacity function $c: E \rightarrow N$, $k$ pairs of  vertices $(s_i,t_i)$ and a demand  function $d:\{1,\ldots, k\} \rightarrow N$.SOLUTION: A flow $f_i\geq d_i$ for  each pair $(s_i,t_i)$ with $f_i \in N$  such that for each $e\in E$,  $$\sum_{i=1}^k f_i(e) \leq c(e) \text.$$
Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two
cc.complexity theory;reference request;graph algorithms;max flow