Thought Exercise: Rational Capacities

Learn how to use the Ford-Fulkerson algorithm when dealing with rational edge capacities.

Changing rational capacities to integers

We know that the Ford-Fulkerson algorithm terminates when the graph has integer capacities. Suppose we are faced with a flow network that has rational numbers as edge capacities. To guarantee that the algorithm terminates, we would like to use the following strategy:

  1. Change the rational capacities to integer values in some systematic way.
  2. Run the Ford-Fulkerson algorithm to find max flow with respect to the changed capacities.
  3. Recover the flow in the flow network with respect to the original rational capacities.

Get hands-on with 1200+ tech skills courses.