Is anyone aware of a max flow algorithm where the edges are conditioned upon one another?

Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.

  • 6
    $\begingroup$ You could express maxflow problem as a linear programming problem. You could add constraints of the form you mentioned to the linear program and then solve it via a general purpose LP solver. $\endgroup$ – Chandra Chekuri Mar 28 '13 at 21:43

The problem you describe is a generalization of the equal flow problem first proposed by Sahni. In addition to the flow network, the input specifies several disjoint sets $R_1, R_2, \dots, R_k$ of arcs; the goal is to find a maximum flow such that for each $i$, all arcs in $R_i$ have the same flow value.

While the fractional version of the equal flow problem can be solved in polynomial time by linear programming, the integer version is NP-hard, even if the capacity of each arc is $1$ and all arcs in each set $R_i$ leave the same vertex $v_i$. Worse, Meyers and Schulz recently proved that there is no polynomial-time $2^{n(1-\epsilon)}$-approximation algorithm, for any fixed $\epsilon>0$, unless $P=NP$. (The integrality gap of the fractional LP can be arbitrarily large.)

  • Carol Meyers and Andreas Schulz. Integer equal flows. Operations Research Letters 37(4):245-249, 2009.

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.