Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911617654980608 |
|---|---|
| author | Haeupler, Bernhard Hladík, Richard Wang, Shengzhe Zhang, Zhijun |
| author_facet | Haeupler, Bernhard Hladík, Richard Wang, Shengzhe Zhang, Zhijun |
| contents | This paper significantly strengthens directed low-diameter decompositions in several ways.
We define and give the first results for separated low-diameter decompositions in directed graphs, tighten and generalize probabilistic guarantees, and prove new independence results between (far away) edges. Our results are the first to give meaningful guarantees for decompositions with small diameters $D = Ω(\log\log n)$ in contrast to the state of the art that only applies to super-logarithmic diameters $D = ω(\log n)$.
These results transfer several important and widely used aspects of undirected low-diameter decompositions to the directed setting. All our results are algorithmic -- small modifications to two existing directed low-diameter decompositions [BFHL25; Li25] can be used to sample decompositions with our new guarantees in near-linear time $\tilde{O}(m)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24565 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation Haeupler, Bernhard Hladík, Richard Wang, Shengzhe Zhang, Zhijun Data Structures and Algorithms This paper significantly strengthens directed low-diameter decompositions in several ways. We define and give the first results for separated low-diameter decompositions in directed graphs, tighten and generalize probabilistic guarantees, and prove new independence results between (far away) edges. Our results are the first to give meaningful guarantees for decompositions with small diameters $D = Ω(\log\log n)$ in contrast to the state of the art that only applies to super-logarithmic diameters $D = ω(\log n)$. These results transfer several important and widely used aspects of undirected low-diameter decompositions to the directed setting. All our results are algorithmic -- small modifications to two existing directed low-diameter decompositions [BFHL25; Li25] can be used to sample decompositions with our new guarantees in near-linear time $\tilde{O}(m)$. |
| title | Stronger Directed Low-Diameter Decompositions with Sub-Logarithmic Diameter and Separation |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.24565 |