Structural Results on Matching Estimation with Applications to Streaming
We study the problem of estimating the size of a matching when the graph is revealed in a streaming fashion. Our results are multifold:1.We give a tight structural result relating the size of a maximum matching to the arboricityα of a graph, which has been one of the most studied graph parameters for matching algorithms in data streams. One of the implications is an algorithm that estimates the matching size up to a factor of (α+ 2) (1 + ε) using O~ (αn2 / 3) space in insertion-only graph streams and O~ (αn4 / 5) space in dynamic streams, where n is the number of nodes in the graph.