Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
David G. Harris · SIAM Journal on Computing · 2019
We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank r. Our main result is a deterministic algorithm to generate a matching which is an O(r)-approximation to the maximum weight matching, running in Õ(r log Δ + log2Δ + log* n) rounds. (Here, the Õ() notations hides polyloglog Δ and polylog r factors). This is based on a number of new derandomization techniques extending methods of Ghaffari, Harris & Kuhn (2017). The first main application is to nearly-optimal algorithms for the long-studied problem of maximum-weight graph matching. Specifically, we get a (1+ε) approximation algorithm using Õ(log Δ/ε3+ polylog(1/ε, log log n)) randomized time and Õ(log2Δ/ε4+ log*n/ε) deterministic time. The second application is a faster algorithm for hypergraph maximal matching, a versatile subroutine introduced in Ghaffari et al. (2017) for a variety of local graph algorithms. This gives an algorithm for (2Δ - 1) -edge-list coloring in Õ(log2Δ log n) rounds deterministically or Õ((log log n)3) rounds randomly. Another consequence (with additional optimizations) is an algorithm which generates an edge-orientation with out-degree at most ⌈(1+ε)λ⌉ for a graph of arboricity λ; for fixed ε this runs in Õ(log6n) rounds deterministically or Õ(log3n ) rounds randomly.