Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916749740343296 |
|---|---|
| author | Khoury, Seri Schild, Aaron |
| author_facet | Khoury, Seri Schild, Aaron |
| contents | In this work, we present an $Ω\left(\min\{\log Δ, \sqrt{\log n}\}\right)$ lower bound for Maximal Matching (MM) in $Δ$-ary trees against randomized algorithms. By a folklore reduction, the same lower bound applies to Maximal Independent Set (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 $Δ$, this shows that the current upper bounds are optimal for a wide range of $Δ\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_15654 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching Khoury, Seri Schild, Aaron Distributed, Parallel, and Cluster Computing Data Structures and Algorithms In this work, we present an $Ω\left(\min\{\log Δ, \sqrt{\log n}\}\right)$ lower bound for Maximal Matching (MM) in $Δ$-ary trees against randomized algorithms. By a folklore reduction, the same lower bound applies to Maximal Independent Set (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 $Δ$, this shows that the current upper bounds are optimal for a wide range of $Δ\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. |
| title | Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.15654 |