Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^{O(1/\varepsilon)}$ Queries
Edith Cohen, Mohammad Roghani
A local computation algorithm (LCA) for matching answers ``who is the mate of $v$?'' by inspecting only a small part of the graph, with all answers consistent with one matching. For $n$-vertex graphs of maximum degree $Δ\ge2$, Levi et al. [Algorithmica'17] give a $(1-\varepsilon)$-approximate matching LCA using $(Δ/\varepsilon)^{O(1/\varepsilon^2)} \operatorname{polylog}(n)$ queries per invocation, while Yoshida et al. [SIAM J. Comput.'12] estimate the maximum matching size within additive error $\varepsilon n$ using $Δ^{O(1/\varepsilon^2)}$ queries. Behnezhad, Roghani, and Rubinstein [FOCS'23] proved a $Δ^{Ω(1/\varepsilon)}$ lower bound for both tasks, even on bipartite graphs and even when the LCA's matching guarantee is relaxed to additive $\varepsilon n$ error. This leaves a gap between linear and quadratic dependence on $1/\varepsilon$ in the exponent. We close this gap on bipartite graphs. We give an LCA that answers each mate query with $Δ^{O(1/\varepsilon)}$ queries for a $(1-\varepsilon)$-approximate matching, and an estimator for the maximum matching size within $\varepsilon n$ using $Δ^{O(1/\varepsilon)}$ queries. On general graphs, the same algorithm gives a half-integral fractional matching and estimates the maximum fractional matching size. Our approach runs $O(\varepsilon^{-1}\logΔ)$ rounds of a deterministic local optimization method in which vertices propose to neighbors and update prices according to incoming loads. We design its updates to admit exact recursive sampling with constant expected branching, obtaining the improved randomized bound without exploring full dependency neighborhoods. To our knowledge, this is the first LCA construction based on exact recursive sampling of the iterates of a deterministic continuous optimization method. We expect this approach to have applications beyond matching.
尚无 AI 解读，展示原文摘要