4
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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