



























We study local computation algorithms (LCA) for maximum matching. An LCA does not return its output entirely, but reveals parts of it upon query. For matchings, each query is a vertex $v$; the LCA should return whether $v$ is matched -- and if so to which neighbor -- while spending a small time per query. In this paper, we prove that any LCA that computes a matching that is at most an additive of $εn$ smaller than the maximum matching in $n$-vertex graphs of maximum degree $Δ$ must take at least $Δ^{Ω(1/\varepsilon)}$ time. This comes close to the existing upper bounds that take $(Δ/ε)^{O(1/ε^2)} polylog(n)$ time. In terms of sublinear time algorithms, our techniques imply that any algorithm that estimates the size of maximum matching up to an additive error of $εn$ must take $Δ^{Ω(1/ε)}$ time. This negatively resolves a decade old open problem of the area (see Open Problem 39 of sublinear.info) on whether such estimates can be achieved in $poly(Δ/ε)$ time.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。