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

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

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

(33)

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

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)