Breaking Barriers for Distributed MIS by Faster Degree Reduction
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918029233750016 |
|---|---|
| author | Khoury, Seri Schild, Aaron |
| author_facet | Khoury, Seri Schild, Aaron |
| contents | 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 $\approx 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 $\approx 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\left(\frac{\log Δ}{\log(\log^* Δ)} + \mathrm{poly}(\log\log n)\right)$ rounds, as long as the graph does not contain cycles of length $\leq 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(\sqrt{\log n})$ round algorithm for MIS in trees, refuting a conjecture from the book by Barrenboim and Elkin. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15652 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Breaking Barriers for Distributed MIS by Faster Degree Reduction Khoury, Seri Schild, Aaron Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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 $\approx 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 $\approx 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\left(\frac{\log Δ}{\log(\log^* Δ)} + \mathrm{poly}(\log\log n)\right)$ rounds, as long as the graph does not contain cycles of length $\leq 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(\sqrt{\log n})$ round algorithm for MIS in trees, refuting a conjecture from the book by Barrenboim and Elkin. |
| title | Breaking Barriers for Distributed MIS by Faster Degree Reduction |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.15652 |