Algorithms-1 07

Flow networks, maximum flow problem

Edmonds-Karp algorithm (EK)

Edmonds-Karp algorithm is a special case of the Ford-Fulkerson algorithm. The only change is that instead of choosing a random augmenting path, we will choose the shortest one by the number of edges, found, for example, by BFS. Correctness is already proved, as it is a special case of the Ford-Fulkerson algorithm. The only thing there is to prove is the runtime complexity, which we will prove to be

Minimum distance from source in the residual network lemma

Minimum distance to sink in the residual network lemma

Existence of an augmenting path in the pre-augmented residual network lemma

Saturation of an edge in the residual network lemma

A corollary of this lemma is that there can be at most iterations in each phase. The number of phases is at most Finding the shortest augmented path takes All in all, the runtime complexity of Edmonds-Karp algorithm is

Dinic’s algorithm

Dinic’s algorithm operates with layers/levels, where during the -th phase, there are layers.

The layer graph definition

Building a layer graph requires running a BFS from and a BFS on inverted graph from , in total The layer graph contains all possible shortest augmenting paths in , thus we can choose arbitrary edge between each pair of layers and find a shortest path in time.

Updating the layer graph lemma

During one phase, edge can become saturated, and thus should be removed from the layer graph. Vertices, as a result, can become dead-ends (either no incoming edges or no outgoing edges) and should also be removed. We can efficiently perform deletions by storing two counters for each vertex, for and Each vertex can become a dead-end only once per phase, and each edge can be removed only once per phase, consequently, there will be at most deletions in one phase.

Hopcroft-Karp

Suppose there is also a vertex capacity function

This new problem can be reduced to the regular edge-only capacity max flow problem with the following:

Assume now, . We will call such flow networks, the networks with unit vertex-capacities.

Upper bound on the flow value in unit vertex-capacities networks lemma

Running the Dinic algorithm on such a flow network yields the same (for now) runtime. Note however, once an edge is used in an augmenting path, it is immediately saturated and both become dead-ends. This means that all augmenting paths in will be vertex-disjoint. It is possible to find the maximum set of vertex-disjoint augmenting paths in . This gives us an upper bound of for the whole algorithm. Given the parameter for the number of phases, we can use the following algorithm