language: en

Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching

David R. Karger * and Matthew S. Levine *

Abstract Consider an n-vertex, m-edge, undirected graph with maximum flow value v. We give a method to find augmenting paths in such a graph in amortized sub-linear (O(n p v)) time per path. This lets us improve the time bound of the classic augmenting path algorithm to O(m + nv 3=2 ) on simple graphs. The addition of a blocking flow subroutine gives a simple, deterministic O(nm 2=3 v 1=6 )-time algorithm. We also use our technique to improve known randomized algorithms, giving O(m+nv 5=4 )-time and O(m+n 11=9 v)-time algorithms for capacitated undirected graphs. For simple graphs, in which v n, the last bound is O(n 2:2 ), improving on the best previous bound of O(n 2:5 ), which is also the best known time bound for bipartite matching.

1 Introduction