Algorithm improves memory for matching size in special streaming graphs
Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using $\tilde{O}(n^{2/3})$ space
Data Structures and Algorithms
Summary
Finding the largest set of edges without overlaps, called maximum matching, is important for understanding networks like social or communication graphs. These networks can change over time with additions and removals of connections, so algorithms need to handle updates efficiently using limited memory. The authors created a new method that better estimates the maximum matching size using less memory for graphs that are not too complex, measured by a property called arboricity. Their approach works in one pass and doesn’t require knowing limits on deletions or complexity during the process.
What this means in practice
- •For network engineers: Estimate maximum matching in large dynamic networks with limited memory to optimize connectivity analysis efficiently.
- •For database administrators: Improve space usage in streaming graph database queries by approximating matchings in minimally connected data graphs.
Authors
Andrew McGregor
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.