# Max flow with conditional edges

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.

• 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. – 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.)