On the efficiency of maximum-flow algorithms on networks with small integer capacities (Q1111460)

The performance of maximum-flow algorithms that work in phases is studied as a function of the maximum arc capacity, C, of the network and a quantity we call the total potential, P, of the network, which is related to the average amount of flow that can be sent through a node. Extending results by \textit{S. Even} and \textit{R. E. Tarjan} [SIAM J. Computing 4, 507-518 (1975; Zbl 0328.90031)] we derive a tight \(O(\min \{C^{1/3}| V|^{2/3},P^{1/2},| V| \})\) upper bound on the number of phases. An O(min\(\{\) P log\(| V|,C| V|^{3/2},| V|^ 2| E| \})\) upper bound is derived on the total length of the augmenting paths used by Dinic's algorithm. The latter quantity is useful in estimating the performance of Dinic's method on certain inputs. Our results show that on a natural class of networks, the performance of Dinic's algorithm is significantly better than would be apparent from a bound based on \(| V|\) and \(| E|\) alone. We present an application of our bounds to the maximum subgraph density problem.