{"ID":22952808,"CreatedAt":"2026-09-17T02:12:05.498442134Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19136","arxiv_id":"2609.19136","title":"Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using $\\tilde{O}(n^{2/3})$ space","abstract":"The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\\varepsilon)(α+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $α$. The algorithm uses $O(\\varepsilon^{-4/3}α^{4/3}n^{2/3} \\text{polylog} n)$ space. For constant $α$ and $\\varepsilon$, this improves the best known previous space bound from $O(n^{4/5} \\text{polylog} n)$ to $O(n^{2/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.","short_abstract":"The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\\varepsilon)(α+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $α$. The algorithm uses $O(\\varepsilon^{-4/3}α^{4/3}n^{2/3} \\text{polylog} n)$ space. For constant $α$ and $\\varepsilo...","url_abs":"https://arxiv.org/abs/2609.19136","url_pdf":"https://arxiv.org/pdf/2609.19136v1","authors":"[\"Andrew McGregor\"]","published":"2026-09-16T17:56:37Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}