Consider the max-flow problem with a set of additional constraints, each in the following form: the flow on edge $e$ must equal the flow on edge $e'$. My question is how to modify existng max-flow algo to solve this variant.
1
-
$\begingroup$ It is very unlikely that you can modify normal graph theoretic max-flow algorithms for your variant. For example, even when the capacities are integer valued, the only feasible max-flow could have fractional value. This implies that for example a variation of Ford-Fulkerson would not work. $\endgroup$– AspiringMatNov 2, 2022 at 6:54
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
One way to solve the max-flow problem is that of considering the its linear programming formulation and using any algorithm to solve linear-programs.
Given a directed graph $G=(V,E)$, a source $s \in V$ with no incoming edges, a sink $t \in V$ with no outgoing edges, and a non-negative capacity $c_e$ for each edge $e \in E$, the formulation has one variable $f_e \in \mathbb{R}$ for each edge $e \in E$ and it is as follows: $$ \max \sum_{(s,v) \in E}f_{(s,v)} \quad \mbox{s.t.} \\ 0 \le f_e \le c_e \quad \forall e\in E \\ \sum_{(u,v) \in E} f_{(u,v)} = \sum_{(v,u) \in E} f_{(u,v)} \quad \forall v \in V \setminus \{s,t\} $$ You can directly add your constraints to this formulation in the form $ f_e = f_{e'} $.
-
$\begingroup$ Thank you Steven. Yes, your solution is definately right, but my question is more about how to adapt the graph theoretical max-flow algorithms instead of relying on the LP formualtion. $\endgroup$– lchenOct 31, 2022 at 4:20
-
$\begingroup$ @lchen Why do you think that would even be possible? $\endgroup$– Pål GDNov 2, 2022 at 7:27
-
$\begingroup$ This doesn't answer the question; The question asked for how to modify existing max-flow algo to solve this variant. $\endgroup$ Nov 2, 2022 at 21:56
-
$\begingroup$ Writing down the problem as a LP and then using, e.g., the ellipsoid method (or any other method for solving LPs) is an existing algorithm for solving max flow. $\endgroup$– StevenNov 3, 2022 at 8:09
-
$\begingroup$ Your answer is definately correct, while I am looking for more graphy solutions. $\endgroup$– lchenNov 3, 2022 at 9:33