2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\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
    Commented Feb 15, 2015 at 20:37
  • $\begingroup$ How about just using LP? $\endgroup$
    – Dima Pasechnik
    Commented Feb 15, 2015 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
    Commented Feb 16, 2015 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
    Commented Feb 16, 2015 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
    Commented Feb 16, 2015 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .