On estimating maximum matching size in graph streams

DOI10.1137/1.9781611974782.113MaRDI QIDQ4575856zbMATH OpenOpenAlexFDO

Authors Sepehr Assadi, Sanjeev Khanna, Yang Li

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1701.04364

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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 $alpha$-approximate estimate of the matching size can be computed in dynamic streams using $widetildeO(n^2/alph{a}^4)$ space, and in insertion-only streams using $widetildeO(n/alph{a}^2)$-space. On the lower bound front, we prove that any $alpha$-approximation algorithm for estimating matching size in dynamic graph streams requires $Omega(sqrtn/alph{a}^{2.5})$ bits of space, even if the underlying graph is both sparse and has arboricity bounded by $O(alpha)$. We further improve our lower bound to $Omega(n/alph{a}^2)$ in the case of dense graphs. Furthermore, we prove that a $(1+epsilon)$-approximation to matching size in insertion-only streams requires RS$(n)cdot{n}^{1-O(epsilon)}$ space; here, RS$n$ denotes the maximum number of edge-disjoint induced matchings of size $Theta(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/logn$. 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 $n^{2-O(epsilon)}$ for $(1+epsilon)$-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 $n^{2-O(epsilon)}$ bit lower bound for $(1+epsilon)$-approximation of matrix ranks for dense matrices in dynamic streams, answering an open question of Li and Woodruff (STOC 2016).

Recommendations

• Structural results on matching estimation with applications to streaming
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Sublinear estimation of weighted matchings in dynamic data streams
• Approximating matching size from random streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

Cited in

(30)

• Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model
• scientific article; zbMATH DE number 7250148 (Why is no real title available?)
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Querying a Matrix Through Matrix-Vector Products.
• Optimality of linear sketching under modular updates
• Streaming graph algorithms in the massively parallel computation model
• Sublinear estimation of weighted matchings in dynamic data streams
• scientific article; zbMATH DE number 7650137 (Why is no real title available?)
• Approximate Maximum Matching in Random Streams
• scientific article; zbMATH DE number 7758324 (Why is no real title available?)
• Structural results on matching estimation with applications to streaming
• Graph sketching and streaming: new approaches for analyzing massive graphs
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Improved bounds for matching in random-order streams
• Sketching approximability of all finite CSPs
• On approximating matrix norms in data streams
• Improved bounds for matching in random-order streams
• Sublinear algorithms and lower bounds for metric TSP cost estimation
• Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs
• Streaming algorithms for connectivity augmentation
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• On regularity lemma and barriers in streaming and dynamic matching
• Stochastic minimum vertex cover in general graphs: a 3/2-approximation
• Matchings in low-arboricity graphs in the dynamic graph stream model
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• Weighted matching in the random-order streaming and robust communication models
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Approximating matching size from random streams
• Maximum matching in two, three, and a few more passes over graph streams

This page was built for publication: On estimating maximum matching size in graph streams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575856)