Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I know that a max flow problem for undirected graphs has a standard reduction to directed graphs in order to apply Ford–Fulkerson algorithm and getting a feasible solution.
Here's my doubt. An undirected edge $(u,v)$ with capacity $1$, will correspond to two directed edges $(u,v), (v,u)$ both with capacity $1$. However, the solution cannot use both edges since I would lose the correspondence with the original problem.
What am I missing?
If a flow somehow uses both $(u, v)$ and $(v, u)$, it is equivalent to another flow that only uses one of them. So if $f_{uv} \ge f_{vu} > 0$, treat it as the equivalent flow $\hat{f}$ where $\hat{f}_{a} = f_a$ for $a\notin\lbrace (u, v), (v, u) \rbrace$, $\hat{f}_{vu} = 0$ and $\hat{f}_{uv} = f_{uv} - f_{vu}$.
I'm tempted to say that this will not happen -- that a maximal flow will always use at most one of $(u,v)$ and $(v,u)$ -- but in some cases that might depend on the efficiency (or dopiness) of the algorithm being used to compute it.
