Abstract
Finding a large matching is the most well-studied graph problem in the data stream model. To bypass the Ω(n) lower bound required to store a matching, recent research has begun to focus on only approximating the size of matchings, resulting in several algorithms with sublinear space bounds. We continue this line of work and present several results for estimating matchings in low arboricity graphs using o(n) space. We give three structural results relating the size of a maximum matching to the arboricity α of a graph and show how those lead to approximation algorithms in different streaming models. For dynamic (insert-delete) streams, we present an algorithm returning (α+2)(1+ ε) approximation of the size of the matching using space O(α ε-2 n4/5 polylog n). For insert-only streams, we show that the same approximation factor can be achieved in merely O(ε-2 log n) space. And finally, we further improve the approximation factor to (α+2) and space to O(1) in adjacency list streams, where edges incident to the same vertex arrive together.