Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.24954 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914123372036096 |
|---|---|
| author | Bernstein, Aaron Fleischmann, Henry Gutenberg, Maximilian Probst Haeupler, Bernhard Hoppenworth, Gary Jiang, Yonggang Li, George Z. Pettie, Seth Saranurak, Thatchaphol Schiller, Leon |
| author_facet | Bernstein, Aaron Fleischmann, Henry Gutenberg, Maximilian Probst Haeupler, Bernhard Hoppenworth, Gary Jiang, Yonggang Li, George Z. Pettie, Seth Saranurak, Thatchaphol Schiller, Leon |
| contents | We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph $G=(V,E)$ with $m$ edges, we can add $m^{1+o(1)}$ ``shortcut'' edges $E_+$ from the transitive closure $E^*$ of $G$ so that $\text{dist}_{G_+}(u,v) \leq m^{o(1)}$ for all $(u,v)\in E^*$, where $G_+=(V,E\cup E_+)$. The conjecture was refuted by Hesse [Hesse, SODA'03], followed by significant efforts in the last few years to optimize the lower bounds.
In this paper we observe that although Hesse refuted the letter of Thorup's conjecture, his work~[Hesse, SODA'03] -- and all followup work -- does not refute the spirit of the conjecture, which should allow $G_+$ to contain both new (shortcut) edges and new Steiner vertices. Our results are as follows.
(1) On the positive side, we present explicit attacks that break all known shortcut lower bounds when Steiner vertices are allowed.
(2) On the negative side, we rule out ideal $m^{1+o(1)}$-size, $m^{o(1)}$-diameter shortcuts whose ``thickness'' is $t=o(\log n/\log \log n)$, meaning no path can contain $t$ consecutive Steiner vertices.
(3) We propose a candidate hard instance as the next step toward resolving the revised version of Thorup's conjecture.
Finally, we show promising implications. Almost-optimal parallel algorithms for computing a generalization of the shortcut that approximately preserves distances or flows imply almost-optimal parallel algorithms with $m^{o(1)}$ depth for exact shortcut paths and exact maximum flow. The state-of-the-art algorithms have much worse depth of $n^{1/2+o(1)}$ [Rozhoň, Haeupler, Martinsson, STOC'23] and $m^{1+o(1)}$ [Chen, Kyng, Liu, FOCS'22], respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_24954 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reviving Thorup's Shortcut Conjecture Bernstein, Aaron Fleischmann, Henry Gutenberg, Maximilian Probst Haeupler, Bernhard Hoppenworth, Gary Jiang, Yonggang Li, George Z. Pettie, Seth Saranurak, Thatchaphol Schiller, Leon Data Structures and Algorithms We aim to revive Thorup's conjecture [Thorup, WG'92] on the existence of reachability shortcuts with ideal size-diameter tradeoffs. Thorup originally asked whether, given any graph $G=(V,E)$ with $m$ edges, we can add $m^{1+o(1)}$ ``shortcut'' edges $E_+$ from the transitive closure $E^*$ of $G$ so that $\text{dist}_{G_+}(u,v) \leq m^{o(1)}$ for all $(u,v)\in E^*$, where $G_+=(V,E\cup E_+)$. The conjecture was refuted by Hesse [Hesse, SODA'03], followed by significant efforts in the last few years to optimize the lower bounds. In this paper we observe that although Hesse refuted the letter of Thorup's conjecture, his work~[Hesse, SODA'03] -- and all followup work -- does not refute the spirit of the conjecture, which should allow $G_+$ to contain both new (shortcut) edges and new Steiner vertices. Our results are as follows. (1) On the positive side, we present explicit attacks that break all known shortcut lower bounds when Steiner vertices are allowed. (2) On the negative side, we rule out ideal $m^{1+o(1)}$-size, $m^{o(1)}$-diameter shortcuts whose ``thickness'' is $t=o(\log n/\log \log n)$, meaning no path can contain $t$ consecutive Steiner vertices. (3) We propose a candidate hard instance as the next step toward resolving the revised version of Thorup's conjecture. Finally, we show promising implications. Almost-optimal parallel algorithms for computing a generalization of the shortcut that approximately preserves distances or flows imply almost-optimal parallel algorithms with $m^{o(1)}$ depth for exact shortcut paths and exact maximum flow. The state-of-the-art algorithms have much worse depth of $n^{1/2+o(1)}$ [Rozhoň, Haeupler, Martinsson, STOC'23] and $m^{1+o(1)}$ [Chen, Kyng, Liu, FOCS'22], respectively. |
| title | Reviving Thorup's Shortcut Conjecture |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.24954 |