Average-case Analysis of Algorithms for Matchings and Related Problems

We analyze the behavior of augmenting paths in random graphs. Our results show that in almost every graph, any non-maximum 0-1 flow admits a short augmenting path. This enables us to prove that augmenting path algorithms, which are fast in the worst case, also perform exceedingly well on the average. In particular, we show that the O(√(|V|) |E|) algorithms for bipartite and general matchings run in almost linear time with high probability. It is also shown that the expected running time of the matching algorithms is O(|E|) on input graphs chosen uniformly at random from the set of all graphs. We establish that the permanent of almost every bipartite graph can be approximated in polynomial time. We extend our results to the analysis of the running time of Dinic's algorithm for finding factors of graphs