Let G = (V, E) be a graph with n = |V| nodes and m = |E| edges. The t-Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distances between t prespecified pairs of vertices. Recently, this problem has received renewed attention, particularly in the case where t = Θ(n): the n-Pairs Shortest Paths problem. In this setting, new algorithms and conditional lower bounds have been developed by Dalirrooyfard, Jin, Vassilevska Williams, and Wein [FOCS'22], and Chechik, Hoch, and Lifshitz [SODA'25]. In this paper, we present the first algorithm for the n-Pairs Shortest Paths problem in weighted undirected graphs that achieves a (2 - α)k-approximation, for constant α > 0, that runs in Õ(mn^{1/k} + n^{1 + 2/k}) time. Specifically, we present a 1.622k-approximation, improving upon the (2k - 3)-approximation of Chechik, Hoch, and Lifshitz [SODA'25] for graphs that are not super sparse, which answers in the affirmative the open question posed by them. We also develop improved approximation algorithms with better tradeoffs for unweighted graphs and dense weighted graphs that improve upon the results of Dalirrooyfard et al. and Chechik, Hoch, and Lifshitz. Our main technical contribution is the new heavy-edge technique. Using this technique, we transform an algorithm with an approximation guarantee that depends on W_{uv}, the weight of the heaviest edge on the shortest path between u and v, into an algorithm with purely multiplicative approximation that does not depend on W_{uv}.

We study the problem of approximating the length of a shortest cycle in a given graph, known as the girth of the graph. The state-of-the-art approximation algorithms for unweighted graphs by Kadria et al. [SODA'22] and Roditty and Trabelsi [arXiv'25] achieve the following trade-off: for every integer k ≥ 2, there is an Õ(n^{1+2/k}) time algorithm that achieves a (2k/3)-approximation for the girth in unweighted n-node graphs. The first result of this paper is to achieve the same trade-off for m-edge, n-node graphs with non-negative real edge weights: a 2k/3-approximation algorithm running in Õ(m+n^{1+2/k}) time. The dependence on m is unavoidable in weighted graphs. Our result improves on the work of Kadria et al. [SODA'23] and Ducoffe [ICALP'19 and SIDMA'21], who were only able to achieve such a trade-off for some values of k. We also prove new fine-grained lower bounds for girth approximation and related problems in unweighted graphs.

Let $G=(V, E)$ be an undirected $n$-vertices $m$-edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a $(2k-1)$-stretch distance oracle with $O(n^{1+\frac{1}{k}})$ space. The first algorithm runs in $\Ot(\max(n^{1+2/k}, m^{1-\frac{1}{k-1}}n^{\frac{2}{k-1}}))$ time, and improves upon the $\Ot(\min(mn^{\frac{1}{k}},n^2))$ time of Thorup and Zwick [STOC 2001, JACM 2005] and Baswana and Kavitha [FOCS 2006, SICOMP 2010], for every $k > 2$ and $m=Ω(n^{1+\frac{1}{k}+\eps})$. This yields the first truly subquadratic time construction for every $2 < k < 6$, and nearly resolves the open problem posed by Wulff-Nilsen [SODA 2012] on the existence of such constructions. The two other algorithms have a running time of the form $\Ot(m+n^{1+f(k)})$, which is near linear in $m$ if $m=Ω(n^{1+f(k)})$, and therefore optimal in such graphs. One algorithm runs in $\Ot(m+n^{\frac32+\frac{3}{4k-6}})$-time, which improves upon the $\Ot(n^2)$-time algorithm of Baswana and Kavitha [FOCS 2006, SICOMP 2010], for $3 < k < 6$, and upon the $\Ot(m+n^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$-time algorithm of Wulff-Nilsen [SODA 2012], for every $k\geq 6$. This is the first linear time algorithm for constructing a $7$-stretch distance oracle and a $9$-stretch distance oracle, for graphs with truly subquadratic density.\footnote{with $m=n^{2-\eps}$ for some $\eps > 0$.} The other algorithm runs in $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{2}}{\sqrt{k}}})$ time, (and hence relevant only for $k\ge 16$), and improves upon the $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{6}}{\sqrt{k}}+O(k^{-1})})$ time algorithm of Wulff-Nilsen [SODA 2012] (which is relevant only for $k\ge 96$). ...

In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs. For weighted undirected graphs, more than a decade ago, Chechik [PODC'13] presented a ≈ 3.68k-stretch compact routing scheme that uses Õ(n^{1/k}log{D}) local storage, where D is the normalized diameter, for every k > 1. We present a ≈ 2.64k-stretch compact routing scheme that uses Õ(n^{1/k}) local storage on average in each vertex. This is the first compact routing scheme that uses total local storage of Õ(n^{1+1/k}) while achieving a c ⋅ k stretch, for a constant c < 3. In real-world network protocols, messages are usually transmitted as part of a communication session between two parties. Therefore, more than two decades ago, Thorup and Zwick [SPAA'01] considered compact routing schemes that establish a communication session using a handshake. In their handshake-based compact routing scheme, the handshake is routed along a (4k-5)-stretch path, and the rest of the communication session is routed along an optimal (2k-1)-stretch path. It is straightforward to improve the (4k-5)-stretch of the handshake to ≈ 3.68k-stretch using the compact routing scheme of Chechik [PODC'13]. We improve the handshake stretch to the optimal (2k-1), by borrowing the concept of roundtrip routing from directed graphs to undirected graphs. For weighted directed graphs, more than two decades ago, Roditty, Thorup, and Zwick [SODA'02 and TALG'08] presented a (4k+ε)-stretch compact roundtrip routing scheme that uses Õ(n^{1/k}) local storage for every k ≥ 3. For k = 3, this gives a (12+ε)-roundtrip stretch using Õ(n^{1/3}) local storage. We improve the stretch by developing a 7-roundtrip stretch routing scheme with Õ(n^{1/3}) local storage. In addition, we consider graphs with bounded hop diameter and present an optimal (2k-1)-roundtrip stretch routing scheme that uses Õ(D_{HOP}⋅ n^{1/k}), where D_{HOP} is the hop diameter of the graph.

Abstract. Let [Formula: see text] be an [Formula: see text]-node [Formula: see text]-edge weighted undirected graph, where [Formula: see text] is a real length function defined on its edges, and let [Formula: see text] denote the girth of [Formula: see text], i.e., the length of a shortest cycle. We present an algorithm that, for any input, integer [Formula: see text], in [Formula: see text] expected time finds a cycle of length at most [Formula: see text]. This algorithm nearly matches an [Formula: see text]-time algorithm of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492] which applied to unweighted graphs of girth 3. For weighted graphs, this result also improves upon the previous state-of-the-art algorithm that in [Formula: see text] time, where [Formula: see text] is an integral length function, finds a cycle of length at most [Formula: see text] of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492]. For [Formula: see text], this result improves upon the result of Roditty and Tov [ ACM Trans. Algorithms, 9 (2013), pp. 15:1–15:13].

We present several new efficient algorithms for approximating the girth, g, of weighted and unweighted n-vertex, m-edge undirected graphs. For undirected graphs with polynomially bounded, integer, non-negative edge weights, we provide an algorithm that for every integer k ≥ 1, runs in Õ(m + n1 + 1/k log g) time and returns a cycle of length at most 2kg. For unweighted, undirected graphs we present an algorithm that for every k ≥ 1, runs in Õ(n1 + 1/k) time and returns a cycle of length at most 2k[g/2], an almost k-approximation. Both algorithms provide trade-offs between the running time and the quality of the approximation. We also obtain faster algorithms for approximation factors better than 2, and improved approximations when the girth is odd or small (e.g., 3 and 4).