On Estimating Maximum Matching Size in Graph Streams
Authors:
Sepehr Assadi, Sanjeev Khanna, Yang Li.
Conference:
The 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17).
This paper resolves an open question of Li and Woodruff in [LW'16] on proving super-linear lower bounds for matrix rank estimation in data streams.
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 O(n^2/α^4) space, and in insertion-only streams using O (n/α^2)-space. These bounds respectively 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 Ω(√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 establish 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 (1 + ε)-approximation to matching size requires RS(n) · n^{1−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 (n · poly(log n/ε))-space algorithm for (1 + ε)-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 n^{2−O(ε)} 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 n^{2−O(ε)} bit lower bound for (1 + ε)-approximation of matrix ranks for dense matrices in dynamic streams, answering an open question of Li and Woodruff (STOC 2016).
On the upper bound front, we show that an α-approximate estimate of the matching size can be computed in dynamic streams using O(n^2/α^4) space, and in insertion-only streams using O (n/α^2)-space. These bounds respectively 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 Ω(√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 establish 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 (1 + ε)-approximation to matching size requires RS(n) · n^{1−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 (n · poly(log n/ε))-space algorithm for (1 + ε)-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 n^{2−O(ε)} 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 n^{2−O(ε)} bit lower bound for (1 + ε)-approximation of matrix ranks for dense matrices in dynamic streams, answering an open question of Li and Woodruff (STOC 2016).
Conference version:
[PDF]
Full version:
[arXiv]
Presentation slides:
[PDF]
BibTex:
[DBLP]