1
$\begingroup$

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.

$\endgroup$
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$ Nov 2, 2022 at 6:54

1 Answer 1

2
$\begingroup$

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'} $.

$\endgroup$
5
  • $\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$
    – lchen
    Oct 31, 2022 at 4:20
  • $\begingroup$ @lchen Why do you think that would even be possible? $\endgroup$
    – Pål GD
    Nov 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$
    – Steven
    Nov 3, 2022 at 8:09
  • $\begingroup$ Your answer is definately correct, while I am looking for more graphy solutions. $\endgroup$
    – lchen
    Nov 3, 2022 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.