Maximum matchings in dynamic graph streams and the simultaneous communication model

Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev

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

50 Scopus citations

Abstract

We study the problem of finding an approximate maximum matching in two closely related computational models, namely, the dynamic graph streaming model and the simultaneous multi-party communication model. In the dynamic graph streaming model, the input graph is revealed as a stream of edge insertions and deletions, and the goal is to design a small space algorithm to approximate the maximum matching. In the simultaneous model, the input graph is partitioned across k players, and the goal is to design a protocol where the k players simultaneously send a small-size message to a coordinator, and the coordinator computes an approximate matching. Dynamic graph streams. We resolve the space complexity of single-pass turnstile streaming algorithms for approximating matchings by showing that for any ϵ > 0, O(n2-3ϵ) space is both sufficient and necessary (up to polylogarithmic factors) to compute an ne-approximate matching; here n denotes the number of vertices in the input graph. The simultaneous communication model. Our results for dynamic graph streams also resolve the (per-player) simultaneous communication complexity for approximating matchings in the edge partition model. For the vertex partition model, we design new randomized and deterministic protocols for k players to achieve an a-approximation. Specifically, for a ≥ √k, we provide a randomized protocol with total communication of 0(nk/a2) and a deterministic protocol with total communication of 0(nk/a). Both these bounds are tight. Our work generalizes the results established by Dobzinski et al. (STOC 2014) for the special case of k = n. Finally, for the case of a = o(y/k), we establish a new lower bound on the simultaneous communication complexity which is super-linear in n.

Original languageEnglish (US)
Title of host publication27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
EditorsRobert Krauthgamer
PublisherAssociation for Computing Machinery
Pages1345-1364
Number of pages20
ISBN (Electronic)9781510819672
DOIs
StatePublished - 2016
Externally publishedYes
Event27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016 - Arlington, United States
Duration: Jan 10 2016Jan 12 2016

Publication series

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

Other

Other27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Country/TerritoryUnited States
CityArlington
Period1/10/161/12/16

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Maximum matchings in dynamic graph streams and the simultaneous communication model'. Together they form a unique fingerprint.

Cite this