Title: Matching Algorithms are Fast in Sparse Random Graphs
Speaker: Guido Schaefer, Technische Universitaet Berlin
When: Thursday, November 17, 4pm-5pm
Where: PPB 300
Abstract:
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum matching has an augmenting path of length $O(\log n)$. This implies that augmenting path algorithms like the Hopcroft–Karp algorithm for bipartite graphs and the Micali–Vazirani algorithm for general graphs, which have a worst case running time of $O(m\sqrt{n})$, run in time $O(m \log n)$ with high probability, where $m$ is the number of edges in the graph. Motwani proved these results for random graphs when the average degree is at least $\ln (n)$ [\emph{Average Case Analysis of Algorithms for Matchings and Related Problems}, Journal of the ACM, \textbf{41}(6), 1994]. Our results hold, if only the average degree is a large enough constant. At the same time we simplify the analysis of Motwani.
Joint work with Holger Bast, Kurt Mehlhorn and Hisao Tamaki
