Source-linked AI summary
Maximum Matching Size for Bounded Arboricity Graphs in the Dynamic Graph Stream Model using $\tilde{O}(n^{2/3})$ space
Andrew McGregor
TL;DR
For bounded-arboricity graphs, maximum matching size can still be as large as n/2, so the literature focuses on estimating it in o(n) space. The algorithm uses recursive and terminal estimates based on node subsampling, alongside a matching-based estimate, in one pass over the insert-delete stream. A one-pass randomized algorithm in the insert-delete graph stream model uses O(ε−4/3α4/3n2/3 polylog n) space to return M_est with high probability.
Problem
For bounded-arboricity graphs, maximum matching size can still be as large as n/2, so the literature focuses on estimating it in o(n) space.
Source: §1 · p. 1Method
The algorithm uses recursive and terminal estimates based on node subsampling, alongside a matching-based estimate, in one pass over the insert-delete stream.
Source: §2.2 · p. 3, §2.3 · p. 3Results
A one-pass randomized algorithm in the insert-delete graph stream model uses O(ε−4/3α4/3n2/3 polylog n) space to return M_est with high probability.
Source: §1 · p. 1Takeaways & Limitations
For ε ∈(0, 1), a one-pass randomized algorithm in the insert-delete graph stream model uses O(ε−4/3α4/3n2/3 polylog n) space to return M_est with high probability.
Source: §1 · p. 1The stream may contain arbitrary insertions and deletions, but the arboricity bound is required only for the final graph.
Source: §1 · p. 1
Abstract
from arXiv · showhide
The paper presents a one-pass algorithm in the insert-delete graph stream model that returns a $(1+\varepsilon)(\alpha+2)$-approximation for the size of the maximum matching in a graph of arboricity at most $\alpha$. The algorithm uses $O(\varepsilon^{-4/3}\alpha^{4/3}n^{2/3} \text{polylog} n)$ space. For constant $\alpha$ 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.
1 Introduction
This section motivates estimating maximum matching size in bounded-arboricity graphs using sublinear space and presents a one-pass dynamic-stream algorithm. Its stated space bound improves on the previous one-pass bound for an O(α)-approximation.
Background
- Dynamic-stream matching has Θ(log log n) pass complexity for constant-factor construction, while adversarial-order insertion-only streams cannot achieve a (1/2 + ε)-approximation in one pass [6,9].These results concern semi-streaming memory; the insertion-only lower bound holds even with randomization.Source: §1 · p. 1
Motivation
- Estimating maximum matching size in o(n) space is the focus for bounded-arboricity graphs, since their maximum matching can still be as large as n/2.Arboricity at most α means every subgraph on t ≥ 1 vertices has at most α(t − 1) edges.Source: §1 · p. 1
Our Result
- O(ε^-4/3 α^4/3 n^2/3 polylog n) space suffices for the paper’s one-pass randomized insert-delete algorithm.The theorem statement says its estimate satisfies a high-probability guarantee, though the guarantee itself is not included in the passage.Source: §1 · p. 1
Previous Work
- The prior best one-pass space bound for an O(α)-approximation in the insert-delete model was Õα,ε(n^4/5).The result is stated for arbitrary insertions and deletions, with only the final graph required to have arboricity at most α.Source: §1 · pp. 1–2
- Earlier one-pass O(α)-approximation in Õα,ε(n^2/3) space required the number of deletions to be O(αn) [26].Other prior algorithms achieved (α + 2)(1 + ε)-approximation in the unrestricted dynamic model with two passes and Õα,ε(n^3/5) space, or three passes and Õα,ε(n^1/2) space.Source: §1 · p. 2
2 Technical Overview
The overview builds on a degree statistic for bounded-arboricity graphs, then develops recursive and terminal estimates for a parameterized regime. It combines those estimates with a matching-based estimate to cover different maximum-matching sizes.
2.1 A Useful Degree Statistic Revisited
- Q is bounded below by the number of vertices with positive f_v, providing a degree-statistic basis for the overview.The passage identifies this statistic as originating in work by Bury et al..Source: §2.1 · p. 2
2.2 Estimation via Recursive Sketching
- For relatively large μ, recursive and terminal estimates are built with one-pass space Õ(K^2), with K set using ε and a sufficiently large constant C0.Recursive sketching samples nested node subsets, estimates level statistics using high-degree corrections identified via CountSketch, and subtracts the estimate from m to form Q̂_rec; the terminal estimate computes the last-level statistic exactly.Source: §2.2 · p. 3
2.3 Combining Estimates (Proof of Theorem 1)
- When K ≤ μ ≤ K², min{K², bQ_rec − ηK} ≥ min{μ, (1 − η)Q − ηK} ≥ (1 − 2η)μ, a lower bound on the capped recursive estimate.Capping estimates and/or subtracting terms accounts for accuracy guarantees that do not hold for all values of μ.Source: §2.3 · pp. 3–4
3 The Terminal and Recursive Estimators
The section builds terminal and recursive estimates of Q from nested node samples. The terminal estimate uses exact degrees in the final sample, while the recursive estimate uses CountSketch degree estimates and correction terms.
3 The Terminal and Recursive Estimators
- The estimators use nested node samples defined by pairwise-independent hash functions, with the final sample having expected size at most K^2.The terminal estimate computes the final-sample degrees exactly; the recursive estimate starts from that level.Source: §3 · p. 4
3.1 The Terminal Estimator
- The terminal estimator takes the median of O(log n) copies, returning an estimate within ηK^2 of Q with high probability while using O~(K^2) worst-case space.If the final sample exceeds 10K^2 nodes, a copy returns an arbitrary value instead of computing all degrees.Source: §3.1 · p. 5
3.2 Degree Estimation via CountSketch
- At most 3µ vertices have degree at least 4α, bounding the number of high-degree vertices relevant to the degree-estimation analysis.The bound follows by considering the endpoints of a maximum matching and applying the arboricity bound.Source: §3.2 · p. 5
- CountSketch estimates sampled-node degrees; clipping and subtracting τ_i/2 before taking the positive part makes the adjusted estimate zero whenever f_v = 0.The method uses CountSketch's frequency estimates and clips them to [0, n − 1].Source: §3.2 · pp. 5–6
3.3 The Recursive Estimator
- The recursive estimator starts from an exact final-level value and adds correction terms to reduce the error accumulated while estimating earlier levels.Its final estimate uses O(log n) independent copies and has worst-case space O~(K^2).Source: §3.3 · pp. 6, 8