Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching

Maximal Independent Set (MIS) and Maximal Matching (MM) play a vital role in distributed symmetry breaking. Despite decades of research, the complexity of both problems in the standard LOCAL model remains unresolved, and several gaps between the best-known upper and lower bounds persist. For n-node graphs with maximum degree $\Delta$, the best current upper bound for randomized algorithms is $O(\log \Delta+\operatorname{poly}(\log \log n))$, shown by Barenboim, Elkin, Pettie, and Schneider for MM [FOCS’12, JACM’16], and by Ghaffari for MIS [SODA’16]. On the other hand, the best-known lower bound for the two problems is $\Omega\left(\min \left\{\sqrt{\frac{\log n}{\log \log n}}, \frac{\log \Delta}{\log \log \Delta}\right\}\right)$, shown by Kuhn, Moscibroda, and Wattenhofer [PODC’04, JACM’16].In this work, we present an $\Omega(\min \{\log \Delta, \sqrt{\log n}\})$ lower bound for MM in $\Delta$-ary trees against randomized algorithms. By a folklore reduction, the same lower bound applies to MIS, albeit not in trees. As a function of n, this is the first advancement in our understanding of the randomized complexity of the two problems in more than two decades. As a function of $\Delta$, this shows that the current upper bounds are optimal for a wide range of $\Delta \in 2^{O(\sqrt{\log n})}$, answering an open question by Balliu, Brandt, Hirvonen, Olivetti, Rabie, and Suomela [FOCS’19, JACM’21].Moreover, our result implies a surprising and counterintuitive separation between MIS and MM in trees, as it was very recently shown that MIS in trees can be solved in $o(\sqrt{\log n})$ rounds. While MIS can be used to find an MM in general graphs, the reduction does not preserve the tree structure when applied to trees. Our separation shows that this is not an artifact of the reduction, but a fundamental difference between the two problems in trees. This also implies that MIS is strictly harder in general graphs compared to trees.Our main technical contribution is a novel technique in which we show that there is a self-reduction from a matching problem in r rounds to the same matching problem in r-1rounds (with slightly weaker probabilistic guarantees). Conceptually, this resembles the celebrated round elimination technique, which transforms an r-round algorithm for a problem $\Pi$ into an (r-1)round algorithm for a different problem $\Pi^{\prime}$. However, our proof differs significantly from the round elimination framework in several fundamental aspects. One of the key concepts we analyze in achieving our result is vertex survival probability, where we show that after $r \ll \min \{\log \Delta, \sqrt{\log n}\}$ rounds, any algorithm that finds a matching must leave two surviving unmatched nodes that are adjacent.