<p>Consider a max-flow network <span class="math-container">$G(V,E,c)$</span>. Consider disjoint subsets of the arcs <span class="math-container">$R_1,…, R_k$</span>. I want to find the maximum <span class="math-container">$s-t$</span> flow such that all the edges in the <span class="math-container">$R_i$</span> have equal flow.</p>
<p>Obviously, this is still polynomial time solvable since the constraints are still linear; we can add additional constraints <span class="math-container">$f_e=f_{e’}$</span> for a fixed <span class="math-container">$e\in R_i$</span> and <span class="math-container">$e'\in R_i$</span>.</p>
<p>My question is whether there is a <em>fast</em> black box reduction to normal max-flow? This would benefit from the near linear time max flow algorithm vs the current matrix-multiplication runtime for LPs.</p>

CC BY-SA 4.0
2022-10-17T12:33:21.010Z
Your constraint is very non-local which makes it perhaps less likely that there will be a reduction to standard max-flow. For instance even when capacities are integer valued max-flow with your constraints can be rational.
Chandra Chekuri
CC BY-SA 4.0
2022-10-18T16:19:27.493Z
OP, maybe edit the question to clarify that you want a *fast* (e.g. nearly linear time) reduction.  E.g. there is a trivial poly-time reduction, and a non-trivial log-space reduction, of your problem to max flow (as max flow is P-complete under log-space reductions).  Conversely, have you looked for a fast reduction from another problem such as 0/1 linear programming *to* your problem?  If there is one that could suggest that what you are looking for is unlikely.
Neal Young
CC BY-SA 4.0
2022-10-18T18:17:36.993Z
@NealYoung Are you saying there is a trivial poly-time reduction from my problem to regular max-flow? I don't see it?
user3508551
CC BY-SA 4.0
2022-10-18T19:23:04.690Z
Sure, here's a trivial poly-time reduction: given an instance I of your problem, solve it in poly time using a poly-time LP algorithm, if the answer is yes, output a small feasible instance of the max-flow problem, otherwise output a small infeasible instance of the max-flow problem.
Neal Young
<linear-programming><max-flow-min-cut><max-flow>
Max-flow while restricting flow on subsets of edges to be equal
user3508551
# Max-flow while restricting flow on subsets of edges to be equal

(Asked by: username_0 on 2022-10-17)

Consider a max-flow network $G(V,E,c)$. Consider disjoint subsets of the arcs $R\_1,…, R\_k$. I want to find the maximum $s-t$ flow such that all the edges in the $R\_i$ have equal flow.

Obviously, this is still polynomial time solvable since the constraints are still linear; we can add additional constraints $f\_e=f\_{e’}$ for a fixed $e\in R\_i$ and $e'\in R\_i$.

My question is whether there is a *fast* black box reduction to normal max-flow? This would benefit from the near linear time max flow algorithm vs the current matrix-multiplication runtime for LPs.

**Tags:** linear-programming, max-flow-min-cut, max-flow
> **Comments:**
> **username_1**: Your constraint is very non-local which makes it perhaps less likely that there will be a reduction to standard max-flow. For instance even when capacities are integer valued max-flow with your constraints can be rational.  
> **username_2**: OP, maybe edit the question to clarify that you want a *fast* (e.g. nearly linear time) reduction.  E.g. there is a trivial poly-time reduction, and a non-trivial log-space reduction, of your problem to max flow (as max flow is P-complete under log-space reductions).  Conversely, have you looked for a fast reduction from another problem such as 0/1 linear programming *to* your problem?  If there is one that could suggest that what you are looking for is unlikely.  
> **username_0**: @NealYoung Are you saying there is a trivial poly-time reduction from my problem to regular max-flow? I don't see it?  
> **username_2**: Sure, here's a trivial poly-time reduction: given an instance I of your problem, solve it in poly time using a poly-time LP algorithm, if the answer is yes, output a small feasible instance of the max-flow problem, otherwise output a small infeasible instance of the max-flow problem.  

---

## 0 answers

