Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a small amount of space? We show that this problem cannot be solved using a nontrivially sublinear (in m) number of samples: m(1-o(1)) samples are needed. On the other hand, O(log(2) n) bits of space suffice to compute an estimate. Our main technical tool is a new peeling type algorithm for matching and its local simulation. We show that a delicate balance between exploration depth and sampling rate allows our simulation to not lose precision over a logarithmic number of levels of recursion and achieve a constant factor approximation. Our algorithm also yields a constant factor approximate local computation algorithm (LCA) for matching with O(d log n) exploration starting from any vertex. Previous approaches were based on local simulations of randomized greedy, which take O(d) time in expectation over the starting vertex or edge (Yoshida et al'09, Onak et al'12), and could not achieve a better than d(2) runtime. Interestingly, we also show that unlike our algorithm, the local simulation of randomized greedy that is the basis of the most efficient prior results does take (Omega) over tilde (d(2)) >> O(d log n) time for a worst case edge even for d = exp(Theta(root log n))