# Multi-commodity flow (or path selection) problem with unit demand complexity

It seems to me that a multi-commodity flow problem should be treated differently when the commodity demand constraint is an equivalence and not a lower-bound. Consider a unit demand. Apparently, in such a case, the problem seems easier (and not really a flow problem).

I am not considering the constraint which relates edges with commodities.

My question is whether this intuition is misleading or not. Is the problem still NP-hard?

EDIT: I'll give the formulation above.

For a given graph $$G = (V,E)$$ with associated capacity function $$c : E \rightarrow \mathbb{N}$$. Let $$K_1, K_2, \dots, K_n$$ be a set of commodities, such that $$K_i = (s_i, t_i)$$ -- i.e. a couple of source and sink nodes in $$V$$ --.

The objective function is a sum over all the flows $$f_{e,i} \in \mathbb{N}$$.

The first constraint is the flow conservation: $$\sum_{e \in \delta^{-}(v)}f_{e,i} - \sum_{e \in \delta^{+}(v)} f_{e,i} = 0,\ \forall i \in \{1,\dots, n\}\text{ and }\forall v \in V\smallsetminus\{s_i,t_i\}.$$

The second constraint is the commodity demand: $$\sum_{e \in \delta^{-}(t_i)}f_{e,i} - \sum_{e \in \delta^{+}(t_i)} f_{e,i} = 1,\ \forall i \in \{1,\dots, n\}.$$

The final constraint is on the capacity bound

$$\sum_{i = 1}^n{f_{e,i}} \leq c(e),\ \forall e \in E$$

• Can u post the full model Jul 29 at 16:31
• What makes you think the problem is easier ? Is it a fact or an intuition? Jul 30 at 18:59
• The fact that, because of the constraints, the flow function is forced to be an $f_{e,i} \in \{0,1\}$. Jul 31 at 18:20
• Your problem is not precisely defined, in particular your notations. With the information you gave, your problem is simply the integer version of the maximum multi-commodity flow problem. Such a problem is NP-hard even with two commodities and unit capacities. Simply check the Wikipedia page for references: en.m.wikipedia.org/wiki/Multi-commodity_flow_problem Aug 1 at 6:15