Michael Kapralov: Approximating Matching Size from Random Streams

We present a streaming algorithm that makes one pass over the edges of an unweighted graph presented in random order, and produces a polylogarithmic approximation to the size of the maximum matching in the graph, while using only polylogarithmic space. Prior to this work the only approximations known were a folklore O~(n√) approximation with polylogarithmic space in an n vertex graph and a constant approximation with Ω(n) space. Our work thus gives the first algorithm where both the space and approximation factors are smaller than any polynomial in n.

Our algorithm is obtained by effecting a streaming implementation of a simple “local” algorithm that we design for this problem. The local algorithm produces a O(k⋅n1/k) approximation to the size of a maximum matching by exploring the radius k neighborhoods of vertices, for any parameter k. We show, somewhat surprisingly, that our local algorithm can be implemented in the streaming setting even for k=Ω(logn/loglogn). Our analysis exposes some of the problems that arise in such conversions of local algorithms into streaming ones, and gives techniques to overcome such problems.

This is joint work with Sanjeev Khanna and Madhu Sudan.