Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model

Authors: Sepehr Assadi, Sanjeev Khanna, Yang Li, Grigory Yaroslavtsev.
Conference: The 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'16).
This paper settles the Open Problem 64 from the List of Open Problems in Sublinear Algorithms.
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, Θ(n^{2−3ε}) space is both sufficient and necessary (up to polylogarithmic factors) to compute an n^ε-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 α-approximation. Specifically, for α ≥ \sqrt{k}, we provide a randomized protocol with total communication of O(nk/α^2) and a deterministic protocol with total communication of O(nk/α). Both these bounds are tight. Our work generalizes the results established by Dobzinski etal. (STOC 2014) for the special case of k = n. Finally, for the case of α = o( k), we establish a new lower bound on the simultaneous communication complexity which is super-linear in n.
Conference version: [PDF]
An earlier version of the paper: [arXiv] (Only contains the results for dynamic graph streams.)
BibTex: [DBLP]