Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:

$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$

where $f(1, 2)$ denotes the flow through arc $(1, 2)$.

Edit: the capacity constraints are disjoint. That is, if S is a set of pairwise disjoint subsets of arcs we have: $\forall B \in S : \sum_{a \in B} c_a f(a) \leq C_B$

Can the problem of computing a maximum flow (or min-cost max flow) for these networks be reduced in a straightforward way to a problem where we have a capacity constraint per arc?

I've found a similar but unanswered question from 2012 here, and Google pointed me towards some articles on shared flow, but this problem seems to be slightly different. Also, parametric max flow seems related, but I don't see how it matches this problem.

Edit: I've just found out about polymatroidal flows, but there seems to be little introductory material. I'd be happy if someone could point me towards an introductory text.


It would be very surprising if such a reduction exists. The reason for the classical max-flow being so rich in structure is that the constraints matrix is totally unimodular in this case. The constraints you add destroy the total unimodularity.

  • $\begingroup$ Thanks, I've been reading a bit today and it seems I need to give up on this reduction, as you point out. I'm not really into the theory around polymatroidal flows, but would those be the right direction to finding an approach to solve this problem? Or perhaps submodular flows? $\endgroup$ – robertdg Feb 15 '15 at 20:37
  • $\begingroup$ How about just using LP? $\endgroup$ – Dima Pasechnik Feb 15 '15 at 20:54
  • $\begingroup$ I'd like to explore combinatorial algorithms first, I consider LP as a final resort. It seems maximum flow can be computed in polynomial time, from the paper Computing maximal "polymatroidal" network flows by Lawler and Martel (Mathematics of Operations Research, vol.7 no.3, august 1982), but minimum cost flow I'm not sure. $\endgroup$ – robertdg Feb 16 '15 at 8:02
  • $\begingroup$ well, LP is polynomial-time too, although not strongly polynomial time. Modern LP solvers are quite fast, IMHO - of course if your network has millions of nodes things get hard... $\endgroup$ – Dima Pasechnik Feb 16 '15 at 9:01
  • $\begingroup$ Right, so let's state that I'm trying to find a strongly polynomial time algorithm for this problem. One thing I forgot to mention is that the sets of arcs that have a "sum" constraint are disjoint. I have the feeling that the problem is really not that more difficult than the regular min cost max flow problem $\endgroup$ – robertdg Feb 16 '15 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.