Integer Multi-Commodity Flow is NP-Hard

The multi-commodity flow problem takes as input a directed graph $G=(V,E)$ with edge capacities $c_e \geq 0$ and $k$ commodities. Each commodity $i$ specifies a source $s_i$, sink $t_i$, and demand $d_i$. A feasible solution assigns non-negative flows $f_i(e)$ satisfying:

• Capacity: $\sum\limits_{i=1}^{k} f_i(e) \leq c_e$ for every edge $e$.
• Conservation: flow in equals flow out at every node that is not $s_i$ or $t_i$.
• Demand: $d_i$ units of commodity $i$ leave $s_i$ and arrive at $t_i$.

The integer version additionally requires $f_i(e) \in \mathbb{Z}_{\geq 0}$. The decision version asks: does an integer feasible solution exist?

Theorem (Even, Itai, Shamir 1976). The decision version of integer multi-commodity flow is NP-complete, even when:

• $k=2$ (only two commodities),
• every edge capacity is $1$, and
• every demand $d_i = 1$.

In other words, even the simplest non-trivial version of the problem admits no polynomial-time algorithm unless $\mathrm{P}=\mathrm{NP}$. This is sharply different from single-commodity flow ($k=1$), where Ford–Fulkerson terminates in polynomial time and returns an integer-valued optimum whenever capacities are integer.