Breaking Barriers for Distributed MIS by Faster Degree Reduction

We study the problem of finding a maximal independent set (MIS) in the standard LOCAL model of distributed computing. Classical algorithms by Luby [JACM’86] and Alon, Babai, and Itai [JALG’86] find an MIS in O(logn) rounds in n-node graphs with high probability. Despite decades of research, the existence of any o(logn)-round algorithm for general graphs remains one of the major open problems in the field. Interestingly, the hard instances for this problem must contain constant-length cycles. This is because there exists a sublogarithmic-round algorithm for graphs with super-constant girth; i.e., graphs where the length of the shortest cycle is ω(1) , as shown by Ghaffari [SODA’16]. Thus, resolving this ≈ 40-year-old open problem requires understanding the family of graphs that contain k-cycles for some constant k. In this work, we come very close to resolving this ≈ 40-year-old open problem by presenting a sublogarithmic-round algorithm for graphs that can contain k-cycles for all k > 6. Specifically, our algorithm finds an MIS in O(logΔ/log(log* Δ) + poly(loglogn)) rounds, as long as the graph does not contain cycles of length ≤ 6, where Δ is the maximum degree of the graph. As a result, we push the limit on the girth of graphs that admit sublogarithmic-round algorithms from k = ω(1) all the way down to a small constant k=7. Moreover, our result has the two further implications. First, it refutes a conjecture about MIS in trees. By combining our algorithm with a low-arboricity-to-low-degree reduction by Barenboim, Elkin, Pettie, and Schneider [JACM’16], we achieve an O(√logn/log(log* n)) -round algorithm in trees. This refutes a conjecture in the book by Barenboim and Elkin that finding an MIS in trees requires Θ(√logn) rounds. Secondly, it separates MIS from Maximal Matching (MM) in trees. Together with a very recent work that shows a Ω(√logn) lower bound for MM in trees, our result implies a surprising and counterintuitive separation between MIS and MM in trees. While MM can only be easier than MIS in general graphs, it becomes strictly harder in trees. This also implies that MIS itself is strictly harder to solve in general graphs than in trees.