# Multi-commodity flow problem reduction

Assume to tackle a particular group of instances for the integral multi-commodity flow problem.

Particularly, given a digraph $$G = (V \cup S \cup T,E)$$, such that $$S, T, V$$ are all disjoint. Furthermore, any $$s_i \in S$$ has only one exiting edge with capacity equal to its demand. Symmetrically, any $$t_i \in T$$ has only one entering edge, with capacity equal to its demand.

My question is, can I reduce the problem to a single-source, single-sink problem? My idea is to add a super-source and a super-sink with demand equals to the sum of original demands.

If this is feasible, I should be able to solve this particular group of instances in polynomial time.

• For an edge leaving $s_i\in S$, you say capacity = demand. Do you mean supply? Also, you said it's a multi-commodity problem. Are you assuming that each source node supplies only one commodity and each sink node consumes only one commodity?
– prubin
Commented Oct 7, 2021 at 16:13
• Not necessarily. The demand is the number of copies of a certain commodity, isn't it? Hence, for a source $s_i$ suppling $d$ "copies" of commodity $i$, there's a sink $t_i$ consuming those $d$ copies. Commented Oct 8, 2021 at 8:15
• So source node $s_i$ supplies only commodity $i$?
– prubin
Commented Oct 9, 2021 at 15:09
• Exactly. My idea was to logically separate the commodity sources and sinks from their node within the graph, by creating fictitious nodes with only exiting edges. Commented Oct 9, 2021 at 15:39
• OK. I'm not sure how separate source (sink) nodes for each commodity translates to "a single-source, single-sink problem", but I think it is possible to model with individual source/sink nodes per product. One thing to keep in mind: if the original graph contains source (sink) nodes that produce (consume) multiple products and if the original arcs into/out of those nodes have capacity limits, you will need to funnel your individual copies of an original source node through a dummy node with outbound arcs having the original capacities, and similarly for dummy nodes preceding your sinks.
– prubin
Commented Oct 9, 2021 at 20:33