On estimating maximum matching size in graph streams

Sepehr Assadi, Sanjeev Khanna, Yang Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

57 Scopus citations

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, which only contain edge insertions, and dynamic streams that allow both insertions and deletions of the edges, and present new upper and lower bound results for both cases. On the upper bound front, we show that an approximate estimate of the matching size can be computed in dynamic streams using eO(n2=4) space, and in insertion- only streams using eO (n=2)space. These bounds respec- tively shave off a factor of from the space necessary to compute an approximate matching (as opposed to only size), thus proving a non-trivial separation between approximate estimation and approximate computation of matchings in data streams. On the lower bound front, we prove that any approximation algorithm for estimating matching size in dynamic graph streams requires ( p 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. These results estab lish the first non-trivial streaming lower bounds for super- constant approximation of matching size. Furthermore, we present the first super-linear space lower bound for computing a (1)approximation of matching size even in insertion-only streams. In particular, we prove that a approximation to matching size requires RS(n) n1-O(") space; here, RS(n) denotes the maximum number of edge-disjoint induced matchings of size (n) in an n-vertex graph. It is a major open problem with far-reaching implications 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. Moreover, using the best known lower bounds for RS(n), our result already rules out any O(n poly(log n="))-space algorithm for approximation of matchings. 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 n2O(") 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 approximation of matrix ranks for dense matrices in dynamic streams, answering an open question of Li and Woodru (STOC 2016).

Original languageEnglish (US)
Title of host publication28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
EditorsPhilip N. Klein
PublisherAssociation for Computing Machinery
Pages1723-1742
Number of pages20
ISBN (Electronic)9781611974782
DOIs
StatePublished - Jan 1 2017
Externally publishedYes
Event28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 - Barcelona, Spain
Duration: Jan 16 2017Jan 19 2017

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume0

Other

Other28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
CountrySpain
CityBarcelona
Period1/16/171/19/17

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'On estimating maximum matching size in graph streams'. Together they form a unique fingerprint.

Cite this