title: An 'increasing Edge' in a network flow
body: <blockquote>
  <p>We are given a network flow, as well as a max flow in the network. An edge would be called <strong>increasing edge</strong> if increasing its capacity in an arbitrary positive number, would also increase the max flow.</p>
  <p>Present an algorithm the finds an increaing edge (if one exists) and runs at $O(n^2)$.</p>
  </blockquote>
  <p>I thought about the following idea -</p>
  <ul>
  <li>Find the minimum cut in the graph, as its given to us with the ford-fulkerson algorithm.</li>
  <li>Increase the capacity of all the edges in the left hand side of the cut by 1.</li>
  <li>Run BFS in the residual network to find if an improved path exists. If one exists, we have an increasing edge. To find it, we have to compare the original network with the new network. <strong>We have to do that n times since we have to check for an improved path every time we increase the capacity by 1.</strong></li>
  </ul>
  <p>Is it correct, an am I in line with the required running time?</p>
  <p>Thank you!</p>