Approximating matching size from random streams

Abstract

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 Õ(pn) 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 e↵ecting 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 = ⌦(log n / log log n). 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.