# Multi-commodity (Integral) flow 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: Here's the formulation. 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 K_i.$$

The commodity demand constraint is given by: $$\sum_{e \in \delta^{-}(s_i)}f_{e,i} - \sum_{e \in \delta^{+}(s_i)} f_{e,i} = -1,\ \forall i \in \{1,\dots, n\}.$$ $$\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 Commented Jul 29, 2021 at 16:31
• What makes you think the problem is easier ? Is it a fact or an intuition? Commented Jul 30, 2021 at 18:59
• The fact that, because of the constraints, the flow function is forced to be an $f_{e,i} \in \{0,1\}$. Commented Jul 31, 2021 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 Commented Aug 1, 2021 at 6:15