A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs

Abstract

We present a data stream algorithm for estimating the size of the maximum matching of a low arboricity graph. Recall that a graph has arboricity $\alpha$ if its edges can be partitioned into at most $\alpha$ forests and that a planar graph has arboricity $\alpha =3$. Estimating the size of the maximum matching in such graphs has been a focus of recent data stream research. A surprising result on this problem was recently proved by Cormode et al. They designed an ingenious algorithm that returned a $(22.5\alpha +6)(1+\epsilon )$ approximation using a single pass over the edges of the graph (ordered arbitrarily) and $O({\epsilon }^{-2}\alpha \cdot \log n\cdot {\log }_{1+\epsilon }n)$ space. In this note, we improve the approximation factor to $(\alpha +2)(1+\epsilon )$ via a tighter analysis and show that, with a modification of their algorithm, the space required can be reduced to $O({\epsilon }^{-2}\log n)$.

An update to the proof of Theorem 3. See paper for details

References in corpus (1)

• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

Cited by in corpus (1)

• Estimating Graph Parameters from Random Order Streams