I'm having trouble solving this one and would really appreciate any help. thank you in advance!
so, the problem is:
given a flow network with integer capacities on the edges and a max flow f on that network, I need to write an algorithm that determine whether there are at least 4 more different max flows on that given network.
I have seen people suggesting to check for cycles in the residual network. so if there is a cycle, the max flow is not unique, hence, there is another max flow "f2" and than we can choose every 0 < x < 1 and set infinite max flows such as (1-x)(|f|) + x|f2|.but, I cant seem to understand why the cycles in the residual network means that the max flow is not unique and also have a really hard time proving the second part is legal. (the infinite max flows)
thanks again!
Best Answer
Let's assume that we have a single source and a single sink (this can be achieved by adding a dummy source connecting all sources, and same for the sink).
Let $G(V, E)$ be our graph. Let $f^1$ and $f^2$ be two maximal flow.
Subtracting the two flows gives a circulation :
Let $f'=f^2-f^1$. For each vertex v, we have : $$\displaystyle \sum_{u\in V} f'_{uv}-\sum_{u\in V} f'_{vu} = \sum_{u\in V} f^2_{uv}-\sum_{u\in V} f^2_{vu} - \left( \sum_{u\in V} f^1_{uv}-\sum_{u\in V} f^1_{vu} \right) = 0$$ because the flow at any vertex is equal (the max flow for the source, -max flow for the sink and 0 for the other vertices). We also have $f^2-f^1 \leq c-f^1 = Rf^1$ (with $Rf^1$ the flow on the residual graph of $f^1$ and $c$ the vector of capacities), so the circulation obtained is a circulation with the weights of the residual graph corresponding to $f^1$ as capacities.
Reciprocally, if we find a circulation $f'$ in our residual graph, it is immediate to show that $f^1 + f' \leq f^1+Rf1 = c$, so $f^1 + f'$ is also a valid flow.
In conclusion, given a maximum flow, we can find all the other maximum flows by finding valid circulations in the residual graph. A non-trivial circulation must contain a cycle, so it is sufficient to check for a cycle in the residual graph to find another maximum flow (if it exists).
Now that you have two distinct max-flows, it is easy to show that any convex combination of valid flows gives another valid flow with same flow value, thus giving you an infinity of maximum flows. However, if you restrict yourself to max-flows with integer values, you must find circulation with integer weights in the residual graph. I don't know if there is an efficient way of enumerating every single one.