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

  • $\begingroup$ Can u post the full model $\endgroup$ Jul 29 at 16:31
  • $\begingroup$ What makes you think the problem is easier ? Is it a fact or an intuition? $\endgroup$
    – Kuifje
    Jul 30 at 18:59
  • $\begingroup$ The fact that, because of the constraints, the flow function is forced to be an $f_{e,i} \in \{0,1\}$. $\endgroup$ Jul 31 at 18:20
  • 1
    $\begingroup$ 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 $\endgroup$ Aug 1 at 6:15

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.