All work should be done on your own. If you discuss this assignment in any way with anyone else, or find help for getting the answer from any source, you must state so clearly at the top of your submission. There should be no working together except to understand the question.
Prove that in any network, there is a way to start with 0 flow, and to add at most m augmenting paths which give you the maximum flow.
An algorithm is needed which eliminates at least one edge from consideration at each iteration.
A simple algorithm is to use a path search algorithm such as depth first search tracking and avoiding repeated edges. Only edges with a non-zero capacity are considered. Once a path is found increase flow along it to the minimum capacity along the path and decrease the capacities by all the edges by that much. The capacity of the minimum edge is now 0 and will not be considered again. Since this removes an edge from consideration each time, it can only be done m times.
The residual flow graph is simply an alternate representation of the flows and capacities in the original flow graph used to find paths more efficiently. The process of reducing the capacities described in the algorithm above could be used to update a residual flow graph by instead of reducing the capacity, moving weight from the forward edge to a residual edge. Since the original search was done on non-zero edges in the original graph these edges exist in the residual graph as well. Doing the search in the original graph however limits the number of edges to be eliminated to m.
Prove that in any network the maximum flow is less than or equal to the current flow plus the combination of the number of edges times the largest flow that can be pushed along any path.
fmax ≤ fcur + (m max(c(mi)))
While it is not always necessary (or even possible) for a flow network to be completely saturated for there to be the maximum flow between s and t, any completely saturated network will provide the maximum flow from s to t. In order to increase flow from s to t, flow has to be increased along some path through the network, and that is not possible in a saturated network where no edges have available capacity.
The flow necessary to saturate a network is the sum of the edge capacities.
fmax ≤ ∑ c(mi) ≤ m max(c(mi)
Use the result of problem #2 to show that after m augmentations by the largest flow augmenting path, you have found at least 1/2 the flow of the network. This can be used to produce an algorithm that is polynomial in n, m and the log of the flow.
The largest flow augmenting path is the path from s to t in the residual flow graph with the maximum minimum capacity edge. Each edge in the network will have a capacity of at most max(c(mi). The slowest growth of the total flow will be when a set of low capacity edges reduce the maximum capacity for an augmenting path. Each time a largest capacity path is added it will convert one of these forward edges to a back edge and removed from consideration. After m iterations even if all the edges are small, at least half will have been explored.
The relationship to the previous equation is unclear to me. It relates the maximum capacity and the maximum flow which makes sense, but then combining those concepts with the largest augmenting flow is unclear because the min cut can be orders of magnitude less than the maximum edge weight.
One major mistake made on this assignment is to assume that the value if the largest augmenting path never increases as you increase by augmenting paths. Show that it is possible to augment along a largest augmenting path in Gf, and have the value of the largest augmenting path in Gf increase after this augmentation.
I'm having trouble finding this because the algorithms seem to essentially consume high capacity edges. All the examples I've tried only decrease the value. This assignment is very late and I need to get it turned in.