2017/01/16 by Sepehr Assadi, Sanjeev Khanna, Assadi, Sepehr +3 · 3 citations
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.1701.04364
openalex publication_date 2017/01/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of estimating the maximum matching size in graphs whose edges are revealed in a streaming manner. We consider both insertion-only streams and dynamic streams and present new upper and lower bound results for both models. On the upper bound front, we show that an α-approximate estimate of the matching size can be computed in dynamic streams using \widetildeO(n2/α4) space, and in insertion-only streams using \widetildeO(n/α2)-space. On the lower bound front, we prove that any α-approximation algorithm for estimating matching size in dynamic graph streams requires Ω(√(n)/α2.5) bits of space, even if the underlying graph is both sparse and has arboricity bounded by O(α). We further improve our lower bound to Ω(n/α2) in the case of dense graphs. Furthermore, we prove that a (1+ε)-approximation to matching size in insertion-only streams requires RS(n) ⋅ n1-O(ε) space; here, RSn denotes the maximum number of edge-disjoint induced matchings of size Θ(n) in an n-vertex graph. It is a major open problem to determine the value of RS(n), and current results leave open the possibility that RS(n) may be as large as n/log n. We also show how to avoid the dependency on the parameter RS(n) in proving lower bound for dynamic streams and present a near-optimal lower bound of n2-O(ε) for (1+ε)-approximation in this model. Using a well-known connection between matching size and matrix rank, all our lower bounds also hold for the problem of estimating matrix rank. In particular our results imply a near-optimal n2-O(ε) bit lower bound for (1+ε)-approximation of matrix ranks for dense matrices in dynamic streams, answering an open question of Li and Woodruff (STOC 2016).