2025/05/21 by Khoury, Seri, Schild, Aaron
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2505.15652
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(log n) rounds in n-node graphs with high probability. Despite decades of research, the existence of any o(log n)-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(loglog n)) 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. This also implies a o(√(log n)) round algorithm for MIS in trees, refuting a conjecture from the book by Barrenboim and Elkin.