Improved algorithms estimate and find matchings in bipartite graphs faster

Optimal LCA and Sublinear Estimation for Bipartite Matching in $Δ^{O(1/\varepsilon)}$ Queries

Data Structures and Algorithms

Summary

Finding pairs in a network, like matching people or jobs, can be tricky when you want to do it quickly without looking at the whole network. The authors improved algorithms that answer matching queries by looking at only a small part of the network, especially for bipartite graphs. Their method uses fewer steps than before while still giving almost the best possible matches or estimates of the maximum matchings. They do this by cleverly combining a deterministic process with a sampling technique that avoids checking too many connections at once.

What this means in practice

  • For network engineers: Run fast local queries to maintain or analyze large bipartite matching structures without inspecting entire networks.
  • For database system developers: Implement efficient approximate match queries on large bipartite datasets using fewer data accesses.

Authors

Edith Cohen, Mohammad Roghani

Abstract

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.