Smallest Multiplicative Stretch for an $\alpha$-APASP Below $\tilde{O}\left(n^{\omega }\right)$ Runtime

Abstract

Dor, Halperin and Zwick [FOCS'96; SICOMP'00] showed that $(2-\epsilon )$-APASP is at least as hard as BMM for every fixed $0<\epsilon <1$. Zwick [FOCS'98; JACM'02] gave a $2$-APASP algorithm in $\tilde{O}(n^{\omega +o(1)}\log W_{\max })$ runtime, where $W_{\max }$ is the maximum edge weight. Bringmann, K{ü}nnemann and W{ę}grzycki [STOC'19] removed this logarithmic factor. Using OpenAI's recent bound $\omega \le \frac{9}{4}$ gives $\tilde{O}\left(n^{\frac{9}{4}+o(1)}\right)$ time. We present two weighted undirected $2$-APASP algorithms. The first uses $(\min ,\max )$-products. Earlier rectangular FMM bounds of Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'24] and Alman, Duan, Vassilevska Williams, Yinzhan Xu, Zixuan Xu and Zhou [SODA'25] give $\tilde{O}(n^{2.36999465})$ runtime, below the previous $\omega \le 2.371177$ of Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog [arXiv'26]. Current rectangular FMM bounds give $\tilde{O}(n^{2.34549151})$, independent of $W_{\max }$. For integer weights, our second algorithm has $\tilde{O}(n^{\omega -\frac{(\omega -2{)}^2}{\omega -1}+o(1)}{\log }^{O(1)}{W}_{\max })$ runtime, with exponent below $\omega$ whenever $\omega >2$. The rectangular bounds of Uzna{ń}ski [arXiv'26] or of Amanov, van den Berg and Zuiddam [arXiv'26] give $\tilde{O}(n^{2.17157288}{\log }^{O(1)}{W}_{\max })$.