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

arXiv: https://arxiv.org/abs/2305.16815 · HTML: https://mlsanity.com/paper/2305.16815/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 May 2023.

## Built on by (most cited first, 1 of 1)

- [Continual Release of Densest Subgraphs: Privacy Amplification & Sublinear Space via Subsampling](https://mlsanity.com/paper/2510.11640/) (2025)

## Abstract (arXiv)

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 Omega(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.