title: Algorithm: Check if max flow is unique
body: <p>A question to the following exercise:</p>
  
  <blockquote>
    <p>Let N = (V,E,c,s,t) be a flow network such that (V,E) is acyclic, and let m = |E|. Describe a polynomial-
    time algorithm that checks whether N has a unique maximum flow, by solving ≤ m + 1 max-flow problems.
    Explain correctness and running time of the algorithm</p>
  </blockquote>
  
  <p>My suggestion would be the following:</p>
  
  <pre><code>run FF (Ford Fulkerson) once and save the value of the flow v(f) and the flow over all egdes f(e_i)
  for each edge e_i with f(e_i)&gt;0:
      set capacity (in this iteration) of this edge c(e_i)=f(e_i)-1 and run FF. 
      If the value of the flow is the same as in the original graph, then there exists another way to push the max flow through the network and we're done - the max flow isn't unique --&gt; return "not unique"
      Otherwise we continue 
  
  we're done with looping without finding another max flow of same value, that means max flow is unique -&gt; return "unique"
  </code></pre>
  
  <p>Any feedback? Have I overlooked some cases where this does not work? </p>