5

Does anyone know the complexity of obtaining the optimal solution to the integral multi-commodity network flow problem with unit demands, integral capacities, but the cost of using an arc varies across different commodities?
As a follow-up, the same question as above but now we also know that the network is a directed acyclic graph.

batwing
  • 1,458
  • 6
  • 15
  • 2
    I assume you know that the multi-commodity flow is NP hard ? If I am not mistaken, having different costs for each commodity is a generalization, and is thus at least as hard. However, having no cycles may significantly change the structure and complexity. You could check out the proof and see if it holds with cycles http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1975/CS/CS0059.pdf – Kuifje Jul 08 '20 at 11:20

0 Answers0