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

  • $\begingroup$ 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. $\endgroup$ – h.a Apr 28 '11 at 20:34

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.