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.)
Presentation slides:
[PDF]