标题： 重新激发Thorup的捷径猜想 显示英文标题

标题： Reviving Thorup's Shortcut Conjecture

摘要： 我们旨在复兴Thorup关于存在具有理想大小-直径权衡的可达性捷径的猜想[Thorup, WG'92]。 Thorup最初询问，给定任何图$G=(V,E)$，有$m$条边，我们能否添加$m^{1+o(1)}$条“捷径”边$E_+$，来自$G$的传递闭包$E^*$，使得对于所有$(u,v)\in E^*$，$\text{dist}_{G_+}(u,v) \leq m^{o(1)}$，其中$G_+=(V,E\cup E_+)$。 该猜想被Hesse [Hesse, SODA'03]反驳，随后几年来人们进行了大量努力以优化下界。 在本文中，我们注意到虽然Hesse反驳了Thorup猜想的字面意思，但他的工作~[Hesse, SODA'03]——以及所有后续工作——并未反驳该猜想的精神，该精神应允许$G_+$包含新的（捷径）边和新的Steiner顶点。 我们的结果如下。 (1) 在积极方面，我们提出了显式的攻击方法，当允许Steiner顶点时，可以打破所有已知的捷径下界。 (2) 在消极方面，我们排除了理想的$m^{1+o(1)}$大小、$m^{o(1)}$直径的捷径，其“厚度”为$t=o(\log n/\log \log n)$，这意味着任何路径都不能包含$t$个连续的Steiner顶点。 (3) 我们提出一个候选困难实例，作为解决修订版Thorup猜想的下一步。 最后，我们展示了有希望的含义。 计算一种近似保持距离或流的捷径的推广的几乎最优并行算法，意味着对于精确捷径路径和精确最大流的几乎最优并行算法具有$m^{o(1)}$的深度。 当前最先进的算法在$n^{1/2+o(1)}$ [Rozhoň, Haeupler, Martinsson, STOC'23] 和$m^{1+o(1)}$ [Chen, Kyng, Liu, FOCS'22] 上的深度要差得多。 显示英文摘要

摘要： 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\v{n}, Haeupler, Martinsson, STOC'23] and $m^{1+o(1)}$ [Chen, Kyng, Liu, FOCS'22], respectively.