# Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two

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.$$

• The requirement of maximum outdegree two can easily be dealt with. Without the requirement, the problem is known to be NP-hard (hal.archives-ouvertes.fr/docs/00/31/39/48/PDF/tableaukorterev.pdf). So yes, the problem is NP-hard. – h.a Apr 28 '11 at 20:34