Sublinear-Space Streaming Algorithms for Estimating Graph Parameters on Sparse Graphs

In this paper, we design sub-linear space streaming algorithms for estimating three fundamental parameters -- maximum independent set, minimum dominating set and maximum matching -- on sparse graph classes, i.e., graphs which satisfy m=O(n) where m,n is the number of edges, vertices respectively. Each of the three graph parameters we consider can have size Ω(n) even on sparse graph classes, and hence for sublinear-space algorithms we are restricted to parameter estimation instead of attempting to find a solution.
We obtain these results:

– Estimating Max Independent Set via the Caro-Wei bound: Caro and Wei each showed λ = Σ_v 1/(d(v) + 1) is a lower bound on max independent set size, where vertex v has degree d(v). If average degree, d‾, is 𝒪(1), and max degree Δ = 𝒪(ε² d‾^-3 n), our algorithms, with at least 1 - δ success probability:

• In online streaming, return an actual independent set of size 1 ± ε times λ. This improves on Halldórsson et al. [Algorithmica '16]: we have less working space, i.e., 𝒪(log ε^-1·log n·log δ^-1), faster updates, i.e., 𝒪(log ε^-1), and bounded success probability.

• In insertion-only streams, approximate λ within factor 1 ± ε, in one pass, in 𝒪(d‾ ε^-2 log n·log δ^-1) space. This aligns with the result of Cormode et al. [ISCO '18], though our method also works for online streaming. In a vertex-arrival and random-order stream, space reduces to 𝒪(log(d‾ ε^-1)). With extra space and post-processing step, we remove the max-degree constraint.

– Sublinear-Space Algorithms on Forests: On a forest, Esfandiari et al. [SODA '15, TALG '18] showed space lower bounds for 1-pass randomized algorithms that approximately estimate these graph parameters. We narrow the gap between upper and lower bounds:

• Max independent set size within 3/2·(1±ε) in one pass and in log^𝒪(1) n space, and within 4/3·(1±ε) in two passes and in 𝒪‾(√n) space; the lower bound is for approx. ≤ 4/3.

• Min dominating set size within 3·(1±ε) in one pass and in log^𝒪(1) n space, and within 2·(1±ε) in two passes and in 𝒪‾(√n) space; the lower bound is for approx. ≤ 3/2.

• Max matching size within 2·(1±ε) in one pass and in log^𝒪(1) n space, and within 3/2·(1±ε) in two passes and in 𝒪‾(√n) space; the lower bound is for approx. ≤ 3/2.