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, on the one hand, 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, a surprisingly space efficient algorithm for processing the samples exists: O(log 2 n) bits of space suffice to compute an estimate.

Our main technical tool is a new peeling type algorithm for matching that we simulate using a recursive sampling process that crucially ensures that local neighborhood information from 'dense' regions of the graph is provided at appropriately higher sampling rates. 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. The previous best result on matching size estimation from random samples was a log O(1) n approximation [Kapralov et al'14], which completely avoided such delicate trade-offs due to the approximation factor being much larger than exploration depth.

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 Ω(d 2 ) O(d log n) time for a worst case edge even for d = exp(Θ( √ log n)).