Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using $\tilde{O}(n^{2\mathrm{/}3})$ space

The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\epsilon )(\alpha +2)$-approximation for the size of the maximum matching in a graph of arboricity at most $\alpha$. The algorithm uses $O({\epsilon }^{-4\mathrm{/}3}{\alpha }^{4\mathrm{/}3}{n}^{2\mathrm{/}3}\text{polylog}n)$ space. For constant $\alpha$ and $\epsilon$, this improves the best known previous space bound from $O(n^{4\mathrm{/}5}\text{polylog}n)$ to $O(n^{2\mathrm{/}3}\text{polylog}n)$. The algorithm is a linear sketch and requires no bounds on the number of deletions or on the arboricity of intermediate graphs.