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.
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityIs 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.
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.)