On the Randomized Locality of Matching Problems in Regular Graphs

The main goal in distributed symmetry-breaking is to understand the locality of problems;
i.e., the radius of the neighborhood that a node needs to explore in order to arrive at its part
of a global solution. In this work, we study the locality of matching problems in the family
of regular graphs, which is one of the main benchmarks for establishing lower bounds on the
locality of symmetry-breaking problems, as well as for obtaining classification results. Our main
results are summarized as follows:
1. Approximate matching: We develop randomized algorithms to show that (1 + ϵ)-
approximate matching in regular graphs is truly local; i.e., the locality depends only on ϵ
and is independent of all other graph parameters. Furthermore, as long as the degree ∆ is
not very small (namely, as long as ∆ ≥ poly(1/ϵ)), this dependence is only logarithmic in
1/ϵ. This stands in sharp contrast to maximal matching in regular graphs which requires
some dependence on the number of nodes n or the degree ∆. We show matching lower
bounds for both results.
2. Maximal matching: Our techniques further allow us to establish a strong separation
between the node-averaged complexity and worst-case complexity of maximal matching in
regular graphs, by showing that the former is only O(1).
Central to our main technical contribution is a novel martingale-based analysis for the ≈ 40-
year-old algorithm by Luby. In particular, our analysis shows that applying one round of Luby’s
algorithm on the line graph of a ∆-regular graph results in an almost ∆/2-regular graph.