Local Computation Algorithms for Maximum Matching: New Lower Bounds
Authors:
- 6 November 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 2322-2335
Abstract
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 $\epsilon n$ smaller than the maximum matching in n-vertex graphs of maximum degree $\Delta$ must take at least $\Delta^{\Omega(1 / \varepsilon)}$ time. This comes close to the existing upper bounds that take $(\Delta / \epsilon)^{O\left(1 / \epsilon^{2}\right)} \operatorname{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 $\epsilon n$ must take $\Delta^{\Omega(1 / \epsilon)}$ 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 $\operatorname{poly}(\Delta / \epsilon)$ time.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples2020
- Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation2019
- New techniques and tighter bounds for local computation algorithmsJournal of Computer and System Sciences, 2016
- Local Computation Algorithms for Graphs of Non-constant DegreesAlgorithmica, 2016
- Space-efficient Local Computation Algorithms2012
- An improved constant-time approximation algorithm for maximum~matchings2009
- Constant-Time Approximation Algorithms via Local Improvements2008
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithmsTheoretical Computer Science, 2007
- Perfect Matchings in Random Graphs with Prescribed Minimal Degree2004
- Probabilistic computations: Toward a unified measure of complexity1977