I am stuck with the following exercise:

Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time?

I am not sure that this is possible.

I understand that we can check in $O(\lvert V \rvert + \lvert E \rvert)$ time whether $f$ is maximal. (Just build the residual graph $G_f$ and check whether there is an augmenting path. This takes $O(\lvert E \rvert)$ time.) But I do not see how to check the uniqueness. Could you please give me a hint?

Edit: Now I have an idea: If we can show that $$f \text{ is unique } \Longleftrightarrow \text{ there are no cycles in $G_f$ containing the source $s$ or the sink $t$}$$ we are done.

The direction $\Longrightarrow$ is trivial: If there was a cycle in $G_f$ containing $s$ or $t$ we can pump the flow through this cycle or leave it out with no consequences, so $f$ is not unique.

But I have no idea how to do the other part. However, I discovered the following theorem that might be useful for this: The "Flow Decomposition Theorem". According to these notes it says:

Any feasible flow $f$ can be decomposed into at most $m$ cycles and $s-t$ paths with non-zero flows. The value of $f$ is equal to the sum of flows over the paths.

Could you please help me?

  • 1
    $\begingroup$ The cycle idea doesn't work for <=, I think, a simple counter example is 1 2 1 1 nodes connected left to right. If all connections have capacity 1, then there are infinitely many maximum flows, yet no cycle is present. $\endgroup$
    – Nearoo
    Nov 30 '21 at 11:13

Your Answer

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

Browse other questions tagged or ask your own question.