2019/07/12 by Michael Kapralov, Slobodan Mitrović, Kapralov, Michael +5 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1907.05725
openalex publication_date 2019/07/12 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
Given a source of iid samples of edges of an input graph G with n\nvertices and m edges, how many samples does one need to compute a constant\nfactor approximation to the maximum matching size in G? Moreover, is it\npossible to obtain such an estimate in a small amount of space? We show that,\non the one hand, this problem cannot be solved using a nontrivially sublinear\n(in m) number of samples: m1-o(1) samples are needed. On the other hand,\na surprisingly space efficient algorithm for processing the samples exists:\nO(\log2 n) bits of space suffice to compute an estimate.\n Our main technical tool is a new peeling type algorithm for matching that we\nsimulate using a recursive sampling process that crucially ensures that local\nneighborhood information from `dense' regions of the graph is provided at\nappropriately higher sampling rates. We show that a delicate balance between\nexploration depth and sampling rate allows our simulation to not lose precision\nover a logarithmic number of levels of recursion and achieve a constant factor\napproximation. The previous best result on matching size estimation from random\nsamples was a \logO(1) n approximation [Kapralov et al'14].\n Our algorithm also yields a constant factor approximate local computation\nalgorithm (LCA) for matching with O(d\log n) exploration starting from any\nvertex. Previous approaches were based on local simulations of randomized\ngreedy, which take O(d) time em in expectation over the starting vertex or\nedge (Yoshida et al'09, Onak et al'12), and could not achieve a better than\nd2 runtime. Interestingly, we also show that unlike our algorithm, the local\nsimulation of randomized greedy that is the basis of the most efficient prior\nresults does take wt\Ω(d2)\≫ O(d\log n) time for a worst case edge\neven for d=\exp(\Θ(\√(\log n))).\n