Skip to main content
1 of 5

Network flows with shared capacities

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) <= 10,

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

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.