1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – prubin ♦
    Oct 7, 2021 at 16:13
  • $\begingroup$ 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. $\endgroup$
    – Daniele Cuomo
    Oct 8, 2021 at 8:15
  • $\begingroup$ So source node $s_i$ supplies only commodity $i$? $\endgroup$
    – prubin ♦
    Oct 9, 2021 at 15:09
  • $\begingroup$ 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. $\endgroup$
    – Daniele Cuomo
    Oct 9, 2021 at 15:39
  • $\begingroup$ 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. $\endgroup$
    – prubin ♦
    Oct 9, 2021 at 20:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.