<p>The problem you describe is a generalization of the <em>equal flow</em> 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.</p>

<p>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&gt;0$, unless $P=NP$.  (The integrality gap of the fractional LP can be arbitrarily large.)</p>

<ul>
<li>Carol Meyers and Andreas Schulz.  <a href="http://web.mit.edu/schulz/www/epapers/ms-orl-2009.pdf" rel="nofollow">Integer equal flows.</a>  <em>Operations Research Letters</em> 37(4):245-249, 2009.</li>
</ul>

CC BY-SA 3.0
2013-03-28T23:27:00.653Z
2013-03-29T01:27:18.097Z
2013-03-29T01:27:18.097Z
Jeffε
<p>Is anyone aware of a max flow algorithm where the edges are conditioned upon one another? </p>

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

CC BY-SA 3.0
2013-03-28T21:43:22.380Z
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
<ds.algorithms><graph-theory><max-flow>
Max flow with conditional edges
mingxiao
# Max flow with conditional edges

(Asked by: username_0 on 2013-03-28)

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*.

**Tags:** ds.algorithms, graph-theory, max-flow

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2013-03-28. Score: 6 | Accepted answer

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.](http://web.mit.edu/schulz/www/epapers/ms-orl-2009.pdf) *Operations Research Letters* 37(4):245-249, 2009.


---

