Abstract
Graph emulators and hopsets are two fundamental concepts for distance approximation. For a given graph \(G\), an \((\alpha,\beta)\)-emulator is a sparse graph on the same vertex set that preserves the distances of \(G\) up to a multiplicative stretch \(\alpha\) and additive stretch \(\beta\). In contrast, an \((\alpha,\beta)\)-hopset is a set of additional edges that, when added to \(G\), ensures that distances can be approximated up to a multiplicative stretch \(\alpha\), using paths containing at most \(\beta\) edges. When \(\alpha = 1+\epsilon\) for arbitrarily small \(\epsilon>0\), these structures are known as near-additive emulators and near-exact hopsets, respectively. Prior work showed that there is a remarkable similarity between the constructions and guarantees of these two objects. In their survey on this topic, Elkin and Neiman [Bull. EATCS 130, 2020] explicitly asked whether one can obtain a general reduction between near-additive emulators and near-exact hopsets. Following that, Kogan and Parter [FOCS, 2022] provided a general reduction from hopsets to emulators and spanners.
In this paper, we address the reverse direction and show that any construction for a near-additive emulator for undirected unweighted graphs can be leveraged as a black box to construct a hopset for an undirected weighted graph with comparable size, stretch, and a hopbound comparable to the emulator’s additive stretch. Specifically, we show that any algorithm that constructs a \((1+\epsilon',\beta)\)-emulator, with \(0 \le \epsilon' \le 1\) and \(\beta \ge 1\), of size \(S_{\mathcal{A}}(n, \epsilon',\beta)\), can be used to obtain a \((1+\epsilon, O(\frac{\beta^2}{\epsilon^2} \ln(\frac{n}{\epsilon})))\)-hopset of size \(O((S_{\mathcal{A}}(n+m\frac{\beta}{\epsilon^2}, \frac{\epsilon}{294},\beta) \frac{1}{\epsilon} + n)\ln(\frac{n}{\epsilon}))\), for any \(0 < \epsilon \le 1\). Therefore, our reduction answers the question of Elkin and Neiman [Bull. EATCS 130, 2020] for sparse graphs and further advances the understanding of the formal connection between these two structures. Designing a reduction resulting in a hopset size that does not depend on \(m\) remains an intriguing open question.
1 Introduction↩︎
Given a graph \(G\), a hopset is a set of additional edges that, when added to \(G\), ensures that for any pair of vertices, an approximate shortest path exists with a bounded number of edges (or hops). They were first formally introduced by Cohen [1] as a tool for efficient parallel computation of approximate shortest paths. And since then they have been central in parallel algorithms [1]–[7], dynamic distance maintenance [8]–[11], and distributed shortest paths computations [3], [12], [13].
Definition 1 (\(h\)-hop distance). Given a graph \(G = (V,E)\). For a pair of vertices \(u,v \in V\), the \(h\)-hop distance \(\mathop{\mathrm{d}}_{G}^{h}(u,v)\) denotes the weight of the shortest path from \(u\) to \(v\) in \(G\) that contains at most \(h\) edges.
Definition 2 (\((\alpha, \beta)\)-hopset). Given a graph \(G = (V,E)\), a multiplicative stretch \(\alpha\ge1\) and a hopbound \(\beta \in \mathbb{N}\), a \((\alpha, \beta)\)-hopset \(F \subseteq V \times V\) is a set of weighted edges, such that \[\forall{u,v \in V} \quad \mathop{\mathrm{d}}_G(u,v) \le \mathop{\mathrm{d}}_{H}^{\beta}(u,v) \le \alpha \cdot \mathop{\mathrm{d}}_{G}(u,v)\] where \(H = (V, E \cup F)\) is the hopset graph. A hopset is called exact if \(\alpha =1\), and near-exact if \(\alpha = 1+\epsilon\) for arbitrarily small \(\epsilon > 0\).
Two other fundamental structures for approximating distances are spanners and emulators. Rather than bounding the number of hops, they instead aim to sparsify the graph, while preserving approximate pairwise distances. Formally, an emulator is defined as follows:
Definition 3 (\((\alpha,\beta)\)-emulator). Given an undirected graph \(G = (V,E)\), a multiplicative stretch \(\alpha \ge 1\) and an additive stretch \(\beta \ge 0\), the graph \(G^* = (V, E^*)\) with \(E^* \subseteq V \times V\) is an \((\alpha,\beta)\)-emulator of \(G\), iff \[\forall_{u,v \in V} \quad \mathop{\mathrm{d}}_G(u,v) \le \mathop{\mathrm{d}}_{G^*}(u,v) \le \alpha \cdot \mathop{\mathrm{d}}_{G}(u,v) + \beta.\] If in addition \(E^* \subseteq E\), then \(G^*\) is a spanner of \(G\).
Peleg and Schäffer first studied multiplicative spanners (where \(\beta = 0\)) in [14], and additive emulators (where \(\alpha = 1\)) were introduced by Dor, Halperin, and Zwick [15]. The concept of near-additive spanners and emulators was later introduced by Elkin and Peleg [16], who showed that one can construct spanners with stretch \(1+\epsilon\) for arbitrarily small \(\epsilon > 0\) and near-linear size, at the cost of allowing a sufficiently large constant additive stretch. In particular, they showed that for every integer \(k \ge 1\), there exists a \((1+\epsilon, \beta)\)-spanner with \(O(\beta \cdot n^{1+1/k})\) edges, where \(\beta = O(\log(k) / \epsilon)^{\log(k)}\). Thorup and Zwick [17] later gave different constructions for near-additive spanners and emulators on undirected, unweighted graphs. A notable property of their construction is that it is universal, i.e., the algorithm is independent of \(\epsilon\), and thus the resulting spanner applies for all \(\epsilon > 0\) simultaneously. Abboud, Bodwin and Pettie [18] provided a lower bound on the trade-off between \(\epsilon\), the additive stretch and the sparsity of emulators.
In recent years, also hopsets for directed graphs have been studied intensively [19]–[21]. Kogan and Parter [19] showed that for any directed graph, there is a near-exact hopset with size \(O(n)\) and a hopbound of \(\tilde{O}(n^{2/5})\), improving upon a long-standing folklore sampling algorithm, that implied a near-exact hopset of size \(O(n)\) with a hopbound of \(\tilde{O}(n^{1/2})\). Bernstein and Wein [20] further improved on this result and showed that one can obtain a linear-sized near-exact hopset with a hopbound of \(\tilde{O}(n^{1/3})\). Bodwin and Hoppenworth [21] showed that the folklore sampling is essentially optimal for exact-hopsets in both directed and undirected graphs.
For undirected graphs, there is an interesting and extensively studied relationship between the constructions of near-additive spanners, emulators, and near-exact hopsets [3], [18], [22]–[26]. Around the same time, Elkin and Neiman [3] and Huang and Pettie [23] independently showed that classic constructions for near-additive spanners and emulators can be used to obtain near-exact hopsets with a constant hopbound. In particular for any integer \(k \ge 1\), Elkin and Neiman [3] gave a construction, inspired by the near-additive spanner construction of [16], that yields a near-exact hopset with hopbound \(O(\log(k) / \epsilon)^{\log(k)}\) and size \(O(n^{1+1/k}\log(n)\log(k))\), while Huang and Pettie [23] showed that the emulator construction of [17], when applied to weighted graphs, yields a near-exact hopset with hopbound \(O(\log(k) /\epsilon)^{\log(k)}\) and size \(O(n^{1+\frac{1}{2k-1}})\). These results were unified by Neiman and Shabat [26], who devised a single algorithm that can provide state-of-the-art hopsets for undirected, weighted graphs with various stretch regimes.
Elkin and Neiman [27] gave an extensive survey on the connection between these objects, where they raised the following question:
[27] "A very interesting open problem is to explain the relationship between near-additive spanners and near-exact hopsets rigorously, i.e., by providing a reduction between these two objects."
Subsequently, Kogan and Parter [28] made significant progress on this question by providing a general reduction from hopsets to emulators, spanners, and distance preservers. While their reduction to distance preservers is a bit more involved, the reduction to emulators and spanners is quite simple.
Let \(G = (V,E)\) be an unweighted \(n\)-vertex Graph. Let \(H^*\) be some \((1+\epsilon,\beta)\)- hopset for \(G\) and let \(G^*\) be a multiplicative spanner with stretch \(t\) for \(G\). Then, \(H^* \cup G^*\) is a \((1+\epsilon, \beta \cdot t)\)-emulator.
This result also extends to spanners, by a standard reduction. More recently, Kogan and Parter [29] initiated progress in the reverse direction, by showing that certain classes of distance preservers can be converted into exact hopsets.
1.1 Our Results↩︎
In this work, we present a general reduction from near-additive emulators to near-exact hopsets, thereby answering the question of [27] in the affirmative for sparse graphs. As our main contribution, we present a general reduction that shows that any emulator construction can be used to obtain a hopset with similar guarantees, formalized as follows.
theoremthmmain Let \(G = (V,E)\) be an undirected weighted graph, with edge weights in \([1,W]\) and let \(0<\epsilon \le 1\). Suppose there exists an algorithm \(\mathcal{A}\) that, for any undirected unweighted \(n\)-vertex graph, constructs an \((\alpha, \beta)\)-emulator, with \(\alpha \ge 1\) and \(\beta \ge 0\), of size at most \(S_{\mathcal{A}}(n,\alpha,\beta)\). Then there exists a \((\alpha(1+24\epsilon), O(\alpha t^2)\ln(nW))\)-hopset of \(G\) of size \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon}, \alpha, \beta) \frac{1}{\epsilon}\ln(nW))\), where \(t = \max(\frac{1}{\epsilon}, \frac{\beta}{\epsilon})\).
A direct consequence of Theorem [thm:main], by setting \(\alpha = 1 + \epsilon\), is the following result for near-additive emulators, thus answering the question raised in [27] for sparse graphs.
Corollary 1. Let \(G = (V,E)\) be an undirected weighted graph, with edge weights in \([1,W]\) and let \(0<\epsilon \le 1\). Assume there exists an algorithm \(\mathcal{A}\) that, for any undirected unweighted \(n\)-vertex graph and any \(0 \le \epsilon' \le 1\), constructs a \((1+\epsilon', \beta)\)-emulator, with \(\beta \ge 1\), of size at most \(S_{\mathcal{A}}(n,\epsilon',\beta)\). Then \(G\) admits a \((1+\epsilon, O(\frac{\beta^2}{\epsilon^2})\ln(nW))\)-hopset of size \(O(S_{\mathcal{A}}(n+m\frac{\beta}{\epsilon^2}, \frac{\epsilon}{49}, \beta)\frac{1}{\epsilon}\ln(nW))\).
Finally, we can make use of the reduction from [3] to remove the maximum weight \(W\) from the log-factor and get the following overall result.
Corollary 2. Let \(G = (V,E)\) be an undirected weighted graph and let \(0<\epsilon \le \frac{1}{2}\). Assume there exists an algorithm \(\mathcal{A}\) that, for any undirected unweighted \(n\)-vertex graph and any \(0 \le \epsilon' \le \frac{1}{2}\), constructs a \((1+\epsilon', \beta)\)-emulator, with \(\beta \ge 1\), of size at most \(S_{\mathcal{A}}(n,\epsilon', \beta)\). Then \(G\) admits a \((1+\epsilon, O(\frac{\beta^2}{\epsilon^2}\ln(\frac{n}{\epsilon})))\)-hopset of size \(O((S_{\mathcal{A}}(n+m\frac{\beta}{\epsilon^2}, \frac{\epsilon}{294}, \beta)\frac{1}{\epsilon} + n)\ln(\frac{n}{\epsilon}))\).
Compared to the “ideal result”, having guarantees as close to the original emulator as possible, our reduction incurs a blowup in the size depending on the number of edges \(m\) in the input graph, the dependence on \(\beta\) in the hopbound is quadratic instead of linear, and our method introduces an additional log-factor in both the size and the hopbound. Although the size of the obtained hopset also depends on \(m\), we believe that this has only a minor impact in practice, as the runtime of typical algorithmic applications usually already depends at least linearly on \(m\) and therefore adding roughly \(m\) additional edges does not change the asymptotic complexity.
1.2 Overview of Techniques↩︎
First, we introduce the notation and relevant definitions, then we give a high-level overview of the techniques used to achieve the reduction.
Notation
In this work, we consider an undirected, weighted graph \(G=(V,E)\) with positive edge weights, where \(V\) is the set of vertices and \(E\) is the set of edges, with \(n := |V|\) and \(m := |E|\). Given an edge \((u,v) \in E\), its weight is denoted by the function \(\mathop{\mathrm{w}}_G \colon E\to\mathbb{R}_{\ge 1}\), and all edge weights lie in the range \([1,W]\). More generally, for any weighted edge set \(F\), we denote the weight of an edge \(e \in F\) by \(\mathop{\mathrm{w}}_F(e)\). Given a path \(\pi\) in \(G\), its weight is defined as \(\mathop{\mathrm{w}}_G(\pi) = \sum_{(u,v)\in\pi} \mathop{\mathrm{w}}_G((u,v))\) and \(|\pi|\) is the number of edges contained in \(\pi\). For any two vertices \(u,v\) on \(\pi\), we denote by \(\pi[u,v]\) the subpath of \(\pi\) between \(u\) and \(v\). For a pair of vertices \(u,v \in V\), the distance \(\mathop{\mathrm{d}}_G(u,v)\) is defined as the minimum weight of any path from \(u\) to \(v\) in \(G\). Such a path with minimum weight is referred to as a shortest path. If no such path exists, we define \(\mathop{\mathrm{d}}_G(u,v) := \infty\).
Reduction
Given a weighted undirected graph \(G = (V, E)\), we organize our construction around distance scales. We consider the scales \([(1+\epsilon)^i, (1+\epsilon)^{i+1})\) for some \(0 < \epsilon \le 1\) and \(i \in \mathbb{N}_0\).
The core idea behind our reduction is to apply a given \((\alpha,\beta)\)-emulator construction, for unweighted undirected graphs, independently at each scale. For every scale \(i\), we define an unweighted graph \(G_i\) that captures the distances in \(G\) at that scale. In particular, we connect pairs of vertices whose distance falls in the given range by a single edge. We then construct an emulator \(M_i\) on \(G_i\). Since the emulators approximate the distances in the unweighted graphs, we can bound the number of hops of the resulting approximate shortest paths, and by appropriately rescaling the weight of these emulator edges, we obtain the approximate distances in the graph \(G\). The hopset \(F\) is then formed by taking the union of these rescaled emulator edges over all distance scales.
To analyze the stretch and hopbound, we show that for any two vertices \(u,v \in V\) we can find a sequence of hop-bounded alternative paths, a shortcut, each skipping a subpath of the shortest path \(\pi\) from \(u\) to \(v\) in \(G\). Every shortcut reduces the remaining distance to \(v\) by a fixed fraction, ensuring that only a logarithmic number of such shortcuts are required. The idea of constructing a sequence of shortcuts follows the strategy used by Bernstein in [8] and later by Henzinger, Krinninger, and Nanongkai in [12].
Next, we consider a single such shortcut. We need to ensure that a sufficiently long consecutive subpath of the shortcut is contained entirely within an emulator \(M_i\) of a single scale. If we concatenate multiple shortcuts from emulators at different scales, the additive stretch \(\beta\) incurred by the emulator construction would appear additionally each time the path “switches” scale. Hence, preventing the need to make such “switches” allows \(\beta\) to be absorbed into the multiplicative stretch. To this end, a primary challenge is to find a sequence of vertices, starting from \(u\), on the path \(\pi\) in \(G\), such that:
two consecutive vertices are connected by a single edge in \(G_i\) and
the last vertex in the sequence is sufficiently far from \(u\).
Then the corresponding emulator \(M_i\) can provide (almost) the entire required shortcut path, and the number of hops is roughly given by \(\alpha k + \beta\), if the aforementioned sequence contains \(k+1\) points. This is non-trivial, as heavy edges (relative to the scale \(i\)) on the path may cause consecutive points in the sequence not to be connected in \(G_i\). Intuitively, we would require a point of the sequence to lie “on” that edge. To address this issue, we subdivide these heavy edges in the graph \(G\) at each scale before defining the unweighted graphs \(G_i\). We implicitly show that the error incurred by this “discretization” of large “continuous” edges is negligible. However, this approach introduces additional vertices and, as a result, the hopset \(F\) must be formally defined on the graph \(G' = (V', E)\), where \(V \subseteq V'\). It is sufficient to require the “hopset guarantees” to hold only for the vertices in \(G\). This leads to the following definition.
Definition 4 (\(T\)-constrained \((\alpha,\beta)\)-hopset). Given an undirected graph \(G = (V,E)\) and a subset of vertices \(T \subseteq V\), for a multiplicative stretch \(\alpha\ge1\), and a hopbound \(\beta \in \mathbb{N}\), a \(T\)-constrained \((\alpha, \beta)\)-hopset is a set of weighted edges \(F \subseteq V \times V\), such that \[\forall{u,v \in T} \quad \mathop{\mathrm{d}}_G(u,v) \le \mathop{\mathrm{d}}_{H}^{\beta}(u,v) \le \alpha \cdot \mathop{\mathrm{d}}_{G}(u,v)\] where \(H = (V, E \cup F)\) is the hopset graph.
To obtain a hopset for the original graph \(G\), we provide a projection that maps the \(V\)-constrained hopset \(F\) of \(G'\) back to a hopset defined entirely on the vertex set of \(G\), while preserving the same stretch and hopbound guarantees. Conceptually, each subdivision vertex in \(V' \setminus V\) represents a specific point “on” some original edge in \(E\), and the idea behind the projection is to shift hopset edges that are incident to such a subdivision vertex to the nearby original vertices in \(V\). Consider such an edge \((u',v') \in F\) , suppose \(u' \in V'\) lies “on” the edge \((u_1, u_2) \in E\) (where possibly \(u' \in V\), in which case \(u' = u_1 = u_2\)), and similarly suppose \(v' \in V'\) lies “on” the edge \((v_1, v_2) \in E\) (again allowing \(v' = v_1 = v_2\), when \(v' \in V\)). We add up to four replacement edges connecting each endpoint \(u_1\), \(u_2\) to \(v_1\) and \(v_2\), to retain paths of the same total weight between vertices in \(V\) in each rescaled \(M_i\) after the removal of the subdivision vertices. Now, we need to ensure that we do not introduce any shortcuts that would lead to underestimating the distances by assigning weight to these new edges accordingly. First, we rename the nodes \(u_1\) and \(u_2\) such that \(u_2\) is the node encountered (first) when traversing the shortest path in \(G'\) restricted to the relevant scale from \(u'\) to \(v'\). We do the same for \(v_1\) and \(v_2\), where \(v_1\) should be encountered (first) when traversing from the path starting from \(v'\). For the new edge \((u_i, v_j)\) with \(i,j \in \{1,2\}\), the weight is set such that the path \(u_1,u', v', v_2\) in \(G' \cup F\) has the same total weight as the path \(u_1, u_i, v_j, v_2\) (consisting of one to three edges) in \(G \cup \{(u_i, v_j)\}\). This process is illustrated in Figure 1.
Originally, the hopset edge \(e\) had to have weights such that \(\mathop{\mathrm{w}}_F(e)\) was at least as large as the total weight of the shortest path from \(u'\) to \(v'\) in the subdivided graph of \(G\) within one scale. Furthermore, that path contained two edge-disjoint subpaths from \(u'\) to \(u_2\) and from \(v_1\) to \(v'\). Therefore, we get that replacing \(e\) with four edges between original nodes in \(V\), as described above, will not introduce any shortcuts.
Roadmap↩︎
The proof of Theorem [thm:main] is split into two main parts; building a hopset on an extended graph with additional vertices and converting it into a hopset on \(G\) while retaining the guarantees on hopbound and stretch. First, we describe the construction of a hopset on the extended graph in Section 2.1. Then, we analyze the resulting size of this hopset in Section 2.2, and in Section 2.3 we consider the resulting stretch and hopbound. In Section 2.4, we provide details of the projection to a hopset on \(G\) and prove that the same guarantees hold.
2 Hopset Reduction↩︎
2.1 Construction↩︎
In this section, we describe the construction of the hopset, which is organized around distance scales of the form \([(1 + \epsilon)^i, (1 + \epsilon)^{i+1})\), for an integer \(i \ge 0\) and \(0<\epsilon\le 1\). Let \(i_\text{max}\) denote the index such that the diameter of the graph falls into the distance scale \([(1+\epsilon)^{i_\text{max}}, (1+\epsilon)^{i_\text{max}+1})\). We therefore only need to consider the indices \(0 \le i \le i_{\text{max}}\), as all higher scales are empty. Since the diameter of \(G\) is bounded by \(nW\), we have \(i_{\text{max}} \le \lceil \log_{1+\epsilon}(nW) \rceil\) distinct distance scales. At each scale \(i\), we first create a subdivision graph \(\tilde{G}_i\) of \(G\) with edge weights bounded relative to the current scale. Over the vertex set of \(\tilde{G}_i\), we then construct an unweighted graph \(G_i\) which connects vertex pairs whose distance lies within the current scale. To bound the number of hops, we use an arbitrary \((\alpha,\beta)\)-emulator of \(G_i\), whose weights are rescaled to approximate the distances in \(G\). The hopset is obtained by taking the union over all distance scales \(i\), of the rescaled emulator edges, together with the auxiliary edges introduced during the subdivision at each scale. In order to ensure the desired hopbound, we define \(t := \max(\frac{1}{\epsilon}, \frac{\beta}{\epsilon})\).
Subdivision Step
Let \(\tilde{G}_i := (\tilde{V}_i, \tilde{E}_i)\) be the graph, obtained from \(G\) by subdividing each edge \(e \in E\) whose weight satisfies
\[\label{equa:subdivisionCondition} \epsilon(1+\epsilon)^i < \mathop{\mathrm{w}}_G(e) \le t (1+\epsilon)^{i+1}\tag{1}\] into \(k\)-segments, with \(k = \left\lceil \frac{\mathop{\mathrm{w}}_G(e)}{\epsilon(1+\epsilon)^i} \right\rceil\).
The edge \(e\) is replaced by a path of \(k\) edges \(e_1,\dots,e_k\), each with weight \(\mathop{\mathrm{w}}_{\tilde{G}_i}(e_j) :=
\frac{\mathop{\mathrm{w}}_G(e)}{k}\) for \(1 \le j \le k\), so that the total weight of the path remains \(\mathop{\mathrm{w}}_G(e)\). Thus, for the edge \(e
= (v,w) =(u_0,u_k)\), we introduce \(k-1\) new vertices \(u_1, \dots, u_{k-1}\), so that \(e_j = (u_{j-1}, u_j)\).
Based on this subdivision, we now define the notion of a vertex’s origin.
definitiondeforigin For any vertex \(u \in \tilde{V}_i\), the origin of \(u\) is defined as: \[\mathop{\mathrm{origin}}(u) := \begin{cases} \{u\} & \text{if } u\in V\\[4pt] \{v,w\} & \text{if u \in \tilde{V}_i \setminus V and u was created in the subdivision of the edge (v,w)\in E.} \end{cases}\]
definitiondefdelta For any vertex \(u \in \tilde{V}_i\) and original endpoint \(x \in \mathop{\mathrm{origin}}(u)\), \(\delta(x, u)\) denotes the distance between \(x\) and \(u\) along the subdivision path.
If \(u \in \tilde{V}_i\setminus V\), suppose that \(u\) was created by subdividing the edge \(e=(v,w) \in E\) into \(k\) edges \(e_1,\dots,e_k\), and let \(u = u_j\) with \(1 \le j < k\) be the \(j\)-th vertex along this path (with \(u_0 = v\) and \(u_k = w\)). Then for each vertex in \(\mathop{\mathrm{origin}}(u) = \{v,w\}\), we define \[\delta(u_j,v) := \sum_{l=1}^{j} \mathop{\mathrm{w}}_{\tilde{G}_i}(e_l) = \frac{j}{k} \mathop{\mathrm{w}}_G(e)\text{,}\; \delta(u_j,w) := \sum_{l=j+1}^{k} \mathop{\mathrm{w}}_{\tilde{G}_i}(e_l) = \frac{k - j}{k} \mathop{\mathrm{w}}_G(e).\]
Otherwise, if \(u \in V\), then \(\delta(u,u) := 0\).
Using these definitions we define the auxiliary edge set \(\tilde{F}_i\) of \(\tilde{G}_i\), as \[\tilde{F}_i = \{ (u,x) \mid u\in \tilde{V}_i \setminus V \wedge x\in \mathop{\mathrm{origin}}(u)\}\] where the weight of each edge is \(\mathop{\mathrm{w}}_{\tilde{F}_i}((u,x)) := \delta(u,x)\). Before we continue with the construction, observe the following important properties of the subdivision graph \(\tilde{G}_i\).
Let \(\pi\) be any path from \(u\) to \(v\) in \(G\). There exists a path \(\tilde{\pi}\) in \(\tilde{G}_i\) between \(u\) and \(v\), such that \(\mathop{\mathrm{w}}_G(\pi) =\mathop{\mathrm{w}}_{\tilde{G}_i}(\tilde{\pi})\).
Proof. This follows immediately from the construction of \(\tilde{G}_i\), where each edge of \(G\) satisfying Eq. 1 is replaced by a sequence of new edges and intermediate vertices in \(\tilde{G}_i\). Thus, the path \(\tilde{\pi}\) can be obtained from \(\pi\) by replacing each such edge with its corresponding sequence of new edges and vertices. Therefore, \(\tilde{\pi}\) connects \(u\) to \(v\) in \(\tilde{G}_i\) and the vertex set of \(\tilde{\pi}\) consists of the vertices of \(\pi\), together with any intermediate vertices introduced during the subdivision step.
Each sequence of new edges in \(\tilde{G}_i\), replacing an edge, has total weight equal to that of the original edge in \(G\). Thus \(\mathop{\mathrm{w}}_{\tilde{G}_i}(\tilde{\pi}) = \mathop{\mathrm{w}}_G(\pi)\) holds. ◻
For every pair of vertices \(u,v \in V\) with \(\mathop{\mathrm{d}}_G(u,v) \le t (1+\epsilon)^{i + 1}\), every edge on the shortest path from \(u\) to \(v\) in \(\tilde{G}_i\) has weight at most \(\epsilon(1+\epsilon)^i\).
Proof. Let \(\tilde{\pi}\) be the shortest path from \(u\) to \(v\) in \(\tilde{G}_i\), which by Observation [obs:weight95tilde-pi] has weight equal to \(\mathop{\mathrm{d}}_G(u,v)\). Consider an edge \(\tilde{e}\) on \(\tilde{\pi}\). If \(\tilde{e} \notin E\), then by construction of \(\tilde{G}_i\), \(\tilde{e}\) is one of \(k = \left\lceil \frac{\mathop{\mathrm{w}}_G(e)}{\epsilon(1+\epsilon)^i} \right\rceil\) edges in the path that replaces some edge \(e \in E\), that satisfied Eq. 1 . Each of these \(k\) edges has weight \(\frac{\mathop{\mathrm{w}}_G(e)}{k} \le \epsilon(1+\epsilon)^i\). Otherwise, if \(\tilde{e} \in E\) we know that \(\tilde{e}\) doesn’t satisfy Eq. 1 . This implies \(\mathop{\mathrm{w}}_{\tilde{G}_i}(\tilde{e}) \le \epsilon(1+\epsilon)^{i+1}\) or \(\mathop{\mathrm{w}}_{\tilde{G}_i}(\tilde{e}) > t(1+\epsilon)^{i+1}\). However, since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) \le t(1+\epsilon)^{i+1}\), the weight of \(\tilde{e}\) is bounded by \(\mathop{\mathrm{w}}_{\tilde{G}_i}(\tilde{\pi}) \le t(1+\epsilon)^{i+1}\), and thus we know that \(\tilde{e}\) has weight at most \(\epsilon(1+\epsilon)^{i}\). ◻
The graph \(\tilde{G}_i\) contains at most \(O(m\frac{t}{\epsilon})\) edges and at most \(O(n+m\frac{t}{\epsilon})\) vertices.
Proof. An edge \(e \in E\) is subdivided if its weight satisfies Eq. 1 , i.e. \(\epsilon (1+\epsilon)^i < \mathop{\mathrm{w}}_G(e) \le t(1+\epsilon)^{i+1}\). In this case, it is replaced by \(k = \left\lceil \frac{\mathop{\mathrm{w}}_G(e)}{\epsilon(1+\epsilon)^i} \right\rceil\) new edges. Since \(\mathop{\mathrm{w}}_G(e) \le t(1+\epsilon)^{i+1}\), \(e\) is divided into at most \(\left\lceil \frac{t(1+\epsilon)^{i+1}}{\epsilon(1+\epsilon)^i} \right\rceil =\left\lceil \frac{t(1+\epsilon)}{\epsilon} \right\rceil \le \frac{t}{\epsilon} (1+\epsilon) + 1 \le \frac{2t}{\epsilon} + 1\) edges in \(\tilde{E}_i\). Hence each edge in \(E\) contributes to \(O(\frac{t}{\epsilon})\) edges, so the total number of edges in \(\tilde{G}_i\) is bounded by \(|\tilde{E}_i| = O(m\frac{t}{\epsilon})\), and the number of vertices by \(|\tilde{V}_i| = O(n+m\frac{t}{\epsilon})\). ◻
Lemma 1. An edge \(e \in E\) can be subdivided in at most \(\log_{1+\epsilon}(\frac{t}{\epsilon}) + 1\) different graphs \(\tilde{G}_i\).
Proof. By definition, an edge \(e \in E\) is subdivided at scale \(i\) if its weight satisfies Eq. 1 , i.e. \(\epsilon (1+\epsilon)^i < \mathop{\mathrm{w}}_G(e) \le t(1+\epsilon)^{i+1}\). For a fixed edge \(e \in E\), we want to bound the number of integer values \(i\) for which this inequality holds. Rewriting the bounds we obtain: \[\begin{align} \epsilon (1+\epsilon)^i < \mathop{\mathrm{w}}_G(e) &\iff i < \log_{1+\epsilon}\left( \frac{\mathop{\mathrm{w}}_G(e)}{\epsilon} \right) \\ \mathop{\mathrm{w}}_G(e) \le t(1+\epsilon)^{i+1} &\iff i \ge \log_{1+\epsilon}\left( \frac{\mathop{\mathrm{w}}_G(e)}{t} \right) - 1. \end{align}\] Thus the number of integer values of \(i\) satisfying Eq. 1 is less than \(\log_{1+\epsilon}(\frac{\mathop{\mathrm{w}}_G(e)}{\epsilon}) - (\log_{1+\epsilon}(\frac{\mathop{\mathrm{w}}_G(e)}{t}) - 1) = \log_{1+\epsilon}(\frac{t}{\epsilon}) + 1\). Therefore, each edge is subdivided in at most \(\log_{1+\epsilon}(\frac{t}{\epsilon}) + 1\) distinct distance scales. ◻
Hopset Definition
Let \(G_i := (\tilde{V}_i, E_i)\) be an unweighted graph, defined over the vertex set \(\tilde{V}_i\) of \(\tilde{G}_i\), which contains an edge for every pair of vertices whose distance in \(\tilde{G}_i\) lies in the \(i\)-th distance scale. Formally, the edge set is given by \(E_i :=\{(u,v) \in \tilde{V}^2_i \mid (1 + \epsilon)^i \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) < (1+\epsilon)^{i+1}\}\). Let \(M_i\) be an \((\alpha,\beta)\)-emulator of \(G_i\). Let \(M_i'\) be the graph obtained by rescaling the weights of \(M_i\) by the upper bound of the current distance scale. Specifically, for each edge \(e \in \mathop{\mathrm{E}}(M_i)\) its weight in \(M_i'\) is given by \(\mathop{\mathrm{w}}_{M_i'} (e) := (1+\epsilon)^{i+1}\mathop{\mathrm{w}}_{M_i}(e)\). Finally, we define the hopset \(F\) as the union of the edge sets of all \(M_i'\) and the auxiliary sets \(\tilde{F}_i\) across distance scales: \[F := \bigcup\limits_{i=0}^{i_{\text{max}}} \mathop{\mathrm{E}}(M_i') \cup \tilde{F}_i.\]
Extended Graph
Since we consider arbitrary emulators \(M_i\) of the unweighted graphs \(G_i = (\tilde{V_i},E_i)\), we make no assumptions about their internal structure. In particular, \(M_i\) may contain edges incident to vertices in \(\tilde{V}_i \setminus V\), which were introduced in the subdivision step and do not appear in the original graph \(G = (V,E)\). Consequently, a path in \(M_i\) from \(u \in V\) to \(v \in V\) may contain such edges, which would not exist in a hopset defined solely on the vertex set \(V\). Hence, to ensure all paths in \(M_i\) correspond to a path in the hopset graph, we need to extend the vertex set of \(G\) by including all new vertices of each graph \(\tilde{G}_i\). Let \(G' := (V',E)\) be the extended graph, with \[V' := \bigcup\limits_{i=0}^{i_{\text{max}}} \tilde{V}_i.\] Thus \(F\) is a \(V\)-constrained hopset of the extended graph \(G'\), and the resulting hopset graph is \(H = (V', E \cup F)\). Note that \(G'\) is obtained from \(G\) by only adding vertices. All vertices in \(V'\setminus V\) are isolated in \(G'\) and only become connected through the edges in \(F\) in the graph \(H\). Thus, the distances and all paths between vertices in \(V\) are identical in \(G\) and \(G'\). Throughout Section 2.3, we may refer to shortest paths in \(G\) for simplicity, even though the hopset is defined on \(G'\).
2.2 Size Analysis↩︎
Next, we analyze the size of the hopset \(F\).
Lemma 2. Let \(\mathcal{A}\) be an algorithm that, for any \(n\)-vertex graph, constructs an \((\alpha,\beta)\)-emulator with \(S_{\mathcal{A}}(n,\alpha,\beta)\) edges. Then the construction in Section 2.1 yields a hopset \(F \subseteq V'\times V'\) which consists of \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon}, \alpha,\beta) \log_{1+\epsilon}(nW) + m\frac{t}{\epsilon}\log_{1+\epsilon}(\frac{t}{\epsilon}))\) edges.
Proof. Using the algorithm \(\mathcal{A}\), each \((\alpha,\beta)\)-emulator \(M_i\) is constructed on the graph \(G_i\). Let \(n_i\) denote the number of vertices in \(G_i\). From Claim [claim:numberEdgesSubG] we know that \(n_i \le n +\frac{2t}{\epsilon} m\). Thus each emulator \(M_i\) contains \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon},\alpha,\beta))\) edges. There are \(i_{\text{max}} \le \log_{1+\epsilon}(nW)\) different distance scales, therefore we have at most \(\log_{1+\epsilon}(nW)\) of such emulators. By Lemma 1 and Claim [claim:numberEdgesSubG], it follows that over all edges and distance scales the number of newly introduced vertices in the subdivision step is \(O(m\frac{t}{\epsilon}\log_{1+\epsilon}(\frac{t}{\epsilon}))\), so the size of the auxiliary edge set \(\tilde{F}\) is also \(O(m\frac{t}{\epsilon}\log_{1+\epsilon}(\frac{t}{\epsilon}))\).4 Thus the total size of the hopset \(F\) is in \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon}, \alpha,\beta) \log_{1+\epsilon}(nW) + m\frac{t}{\epsilon}\log_{1+\epsilon}(\frac{t}{\epsilon}))\). ◻
Note that the size bound stated in Lemma 2 is conservative, as it assumes that every edge gets subdivided at every distance scale \(i\) into the maximum possible number of subedges.
2.3 Hop Reduction↩︎
Let \(G=(V,E)\) be the original graph, and let \(F\) be the edge set as defined in Section 2.1. In this section we show that \(F\) is indeed a \(V\)-constrained \((\alpha(1+24\epsilon),\space O(\alpha t^2)\ln(nW))\)-hopset of \(G'\), for \(t = \max(\frac{1}{\epsilon},\frac{\beta}{\epsilon})\). Let \(\pi\) be a shortest path from \(u\) to \(v\) in \(G\). We will show that there exists a vertex \(w\) on \(\pi\) and an alternative path \(\pi'\) from \(u\) to \(w\) in \(H = (V', E \cup F)\) with the following properties:
The distance from \(u\) to \(w\) in \(G\) is at least \(\Delta t\), with \(\Delta := \frac{\mathop{\mathrm{d}}_G(u,v)}{t^2}\).
The alternative path \(\pi'\) consists of at most \(3t (\alpha + 1)\) edges of \(F\) and includes at most one additional edge from either \(E\) or \(F\).
The weight of the alternative path \(\pi'\) in \(H\) is at most \(\alpha (1 + 24 \epsilon)\) times the distance from \(u\) to \(w\) in \(G\).
Thus, by choosing to take such an alternative path \(\pi'\) from \(u\) to \(w\) instead of a subpath of \(\pi\) we take at most \(3t (\alpha + 1) + 1\) hops, while decreasing the remaining distance to \(v\) by at least \(\Delta t = \frac{\mathop{\mathrm{d}}_G(u,v)}{t}\). However, this introduces an approximation error of \(\alpha(1+24\epsilon)\).
Through repeated application of this strategy with decreasing \(\Delta\), and concatenating the alternative paths, we obtain an alternative path \(\pi''\) in \(H\) from \(u\) to \(v\) (see Figure 2) that has at most \(\ln(nW)\space (3t^2 (\alpha + 1) + t)\) hops. This follows from [item:dist95u95w], which guarantees that with each shortcut we skip a fixed fraction \(\frac{1}{t}\) on the remaining path to \(v\) and [item:alt95path95hops], which limits the number of hops in each shortcut. Property [item:alt95path95weight] ensures that every alternative path has a multiplicative stretch of at most \(\alpha (1 + 24\epsilon)\), and thus the whole path \(\pi''\) also has the same multiplicative stretch. The idea of using such alternative paths to shortcut portions of the shortest path is similar to the approach used in [8], [12].
Before we proceed with the analysis as explained above, we prove two important structural properties of our construction from Section 2.1. For a fixed distance scale \(i\), Claim [claim:up] ensures the existence of a vertex \(u_p\) along the shortest path from \(u\) to \(v\) in the subdivided graph \(\tilde{G}_i\), for which we can guarantee that there exists path from \(u\) to \(u_p\) in the unweighted graph \(G_i\) with a bounded number of edges. For any path in \(G_i\), Claim [claim:weight95hop95emulatorpaths] provides a bound on the weight and number of edges of the corresponding shortest path in the emulator of this distance scale and hence in \(H\).
Let \(\Delta \ge 1\) and let \(i\) be such that \((1+\epsilon)^i \le \Delta < (1+\epsilon)^{i+1}\). Consider any pair of vertices \(u,v \in V\) with \(\mathop{\mathrm{d}}_G(u,v) < \infty\) and \(\mathop{\mathrm{d}}_G(u,v) \ge \Delta t\). Then there exists a vertex \(u_p \in \tilde{V}_i\) on the shortest path from \(u\) to \(v\) in \(\tilde{G}_i\), for some \(0 \le p \le t+t\epsilon\), such that \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) \le \Delta t\) and there is a path of \(p\) edges from \(u\) to \(u_p\) in \(G_i\). Hence \(u_p\) satisfies \(p(1+\epsilon)^i \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) \le p(1+\epsilon)^{i+1}\). Moreover, there is no vertex \(u_p'\) on the remaining subpath from \(u_p\) to \(v\), such that \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,u_p') \ge (1+\epsilon)^i\) and \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u_p') \leq \Delta t\).
Proof. Let \(\tilde{\pi}\) be the shortest path from \(u\) to \(v\) in \(\tilde{G}_i\), which by Observation [obs:weight95tilde-pi] has weight equal to \(\mathop{\mathrm{d}}_G(u,v)\). We iteratively construct a sequence of vertices \(u_0,u_1,\dots,u_p\) along \(\tilde{\pi}\) starting at \(u_0 := u\). For each integer \(j \ge 0\) we define \(u_{j+1}\) to be the first vertex on \(\tilde{\pi}\) after \(u_j\) that satisfies \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_j, u_{j+1}) \ge (1+\epsilon)^i\). If no such vertex exists or \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u_{j+1}) > \Delta t\) we stop and set \(u_p := u_j\). Otherwise, we continue the iteration.
We now show by induction on \(j\) that for every \(0 \le j \le p\), there exists a path of \(j\) edges from \(u\) to
\(u_j\) in \(G_i\).
Base Case. \(j = 0\). Since \(u_0 = u\), the trivial path from \(u\) to \(u_0\) of length \(0\) exists in \(G_i\).
Induction Step. Assume that for any \(j < p\), there exists a path of \(j\) edges from \(u\) to \(u_j\) in \(G_i\). Let \(x\) denote the last vertex on \(\tilde{\pi}\) with \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_j,x) <
(1+\epsilon)^i\), and let \(u_{j+1}\) be its successor. By the choice of \(x\), \(u_{j+1}\) must satisfy \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_j,u_{j+1}) \ge (1+\epsilon)^i\). Since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) \le \Delta t \le t(1+\epsilon)^{i+1}\) Claim [claim:maxEdgeWeightSubG] guarantees that every edge \(e\) on the subpath of \(\tilde{\pi}\) from \(u\) to \(u_p\) has weight \(\mathop{\mathrm{w}}_{\tilde{G}_i}(e) \le \epsilon(1+\epsilon)^i\). Thus, the
distance between \(u_j\) and \(u_{j+1}\) can be upper bounded by \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_j,u_{j+1}) = \mathop{\mathrm{d}}_{\tilde{G}_i}(u_j,x)
+\mathop{\mathrm{w}}_{\tilde{G}_i}((x,u_{j+1})) < (1+\epsilon)^i +\epsilon(1+\epsilon)^i = (1+\epsilon)^{i+1}\). Combining these bounds, we have \((1+\epsilon)^i \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u_j,u_{j+1}) <
(1+\epsilon)^{i+1}\). Therefore, by definition, \(G_i\) contains the edge \((u_j,u_{j+1})\) and and hence there exists a path of \(j+1\) edges from
\(u\) to \(u_{j+1}\) in \(G_i\).
Note that, since there is a path of \(p\) edges from \(u\) to \(u_p\) in \(G_i\) , we have \(p(1+\epsilon)^i \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) \le p(1+\epsilon)^{i+1}\).
Since the constructed final vertex \(u_p\) also satisfies \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u_p) \le \Delta t< t (1+\epsilon)^{i+1}\), we have \(p(1+\epsilon)^i < t (1+\epsilon)^{i+1}\) and it follows directly that \(p < t (1+\epsilon) = t + t\epsilon\). ◻
By the definition of \(G_i\), the guarantees of the emulator \(M_i\) and the definition of weights in \(M_i'\) we get the following claim.
Consider a distance scale \(i \ge 0\). If there exists a path of \(l\) edges between two vertices \(u\),\(v\) in the graph \(G_i\), then there exists a path \(\pi_i\) in \(H = (V', E\cup F)\), with \(|\pi_i| \le \alpha l + \beta\) and \(\mathop{\mathrm{w}}_H(\pi_i) \le (1+\epsilon)^{i+1} (\alpha l + \beta)\).
Proof. Let \(\pi_i\) be the shortest path from \(u\) to \(v\) in the emulator \(M_i\), which is by construction also in \(F\). By definition, this path has weight \(\mathop{\mathrm{w}}_{M_i}(\pi_i) = \mathop{\mathrm{d}}_{M_i}(u,v) \le \alpha \cdot \mathop{\mathrm{d}}_{G_i}(u,v) +\beta \le \alpha l + \beta\). Since all edges have weight at least \(1\), this yields \[\begin{align} |\pi_i| \le \alpha l + \beta. \end{align}\] Recall that in \(M_i'\) all edge weights are scaled by the factor \((1+\epsilon)^{i+1}\). Therefore the weight of the path \(\pi_i\) in \(H\) is \(\mathop{\mathrm{w}}_H(\pi_i) =\mathop{\mathrm{w}}_{M_i'}(\pi_i) = (1+\epsilon)^{i+1} \mathop{\mathrm{w}}_{M_i}(\pi_i)\) and can be bounded by \[\mathop{\mathrm{w}}_H(\pi_i) \le (1+\epsilon)^{i+1} (\alpha l + \beta).\qedhere\] ◻
With Claim [claim:up] and Claim [claim:weight95hop95emulatorpaths], we now show that we can construct a shortcut \(\pi'\) with the desired properties.
Lemma 3. Let \(\Delta > 0\), for every pair of vertices \(u,v \in V\) with \(\mathop{\mathrm{d}}_G(u,v) < \infty\) and \(\mathop{\mathrm{d}}_G(u,v) \ge \Delta t\), we can find a vertex \(w\) on the shortest path from \(u\) to \(v\) in \(G\), and a path \(\pi'\) from \(u\) to \(w\) in \(H = (V', E \cup F)\), such that \(\mathop{\mathrm{d}}_G(u,w) \ge \Delta t\), \(|\pi'| \le 3t (\alpha + 1) + 1\) and \(\mathop{\mathrm{w}}_H(\pi') \le \alpha (1 + 24\epsilon) \cdot \mathop{\mathrm{d}}_G(u,w)\).
Proof. Let \(\pi\) be the shortest path from \(u\) to \(v\) in \(G\). Let \(w'\) be the closest vertex to \(v\) on \(\pi\) for which \(\mathop{\mathrm{d}}_G(u, w') < \Delta t\) still holds, and let \(w\) be its successor on \(\pi\).
In the following proof, we assume \(\Delta \ge 1\), as otherwise the claim follows immediately: Given that all edge weights are at least \(1\) and \(\mathop{\mathrm{d}}_G(u,w') < \Delta t < t\), the shortest path between \(u\) and \(w'\) in \(G\) already consists of at most \(t\) edges. We define the alternative path \(\pi'\) to be the subpath of \(\pi\) from \(u\) to \(w\). Then the guarantees for the number of hops and the stretch hold, since \(|\pi'| = t+1 < 3t (\alpha + 1) + 1\) and \(\mathop{\mathrm{w}}_H(\pi') = \mathop{\mathrm{d}}_G(u,w) \le \alpha(1+24\epsilon) \mathop{\mathrm{d}}_G(u,w)\).
For the remainder of the proof, consider \(i\) such that \((1 + \epsilon)^i \le \Delta < (1+\epsilon)^{i+1}\), that is \(\Delta\) lies in the \(i\)-th distance scale. Let \(\tilde{\pi}\) be the shortest path from \(u\) to \(v\) in \(\tilde{G}_i\), which by Observation [obs:weight95tilde-pi] has weight equal to \(\mathop{\mathrm{d}}_G(u,v)\) and consists of the vertices of \(\pi\), together with any intermediate vertices introduced during the subdivision step. The strategy to construct the path \(\pi'\) with the desired properties from \(u\) to the vertex \(w\) in this case is as follows: First, we identify a vertex \(u'\) on \(\tilde{\pi}\) and a path \(\pi_{\text{pre}}\) in \(H\) from \(u\) to \(u'\) with at most \(3t(\alpha+1)\) hops and a bounded stretch. Then we show that there exists a single edge from \(u'\) to \(w\) in either \(E\) or in \(F\), and by extending \(\pi_{\text{pre}}\) with this edge, we obtain \(\pi'\), whose stretch is at most \(\alpha(1+24\epsilon)\). Let \(u_p\) be the vertex from Claim [claim:up], so that \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) \le \Delta t\) and there exists a path of \(p \le t+t\epsilon\) edges from \(u\) to \(u_p\) in \(G_i\). Let \(\pi_i\) be the path from \(u\) to \(u_p\) in \(H\) guaranteed by Claim [claim:weight95hop95emulatorpaths], with \(\mathop{\mathrm{w}}_H(\pi_i) \le (1+\epsilon)^{i+1}(\alpha p + \beta)\) and \(|\pi_i| \le \alpha p + \beta \le \alpha (t+t\epsilon) + \beta\). Note that \(\pi_i\) may be the trivial path of length \(0\). We will address this case separately when relevant.
The definition of \(u'\) and the path \(\pi_{\text{pre}}\) depend on the position of \(u_p\) relative to \(w'\) along \(\tilde{\pi}\) (see Figure 3). Intuitively, we choose \(u'\) to be a vertex that is at least as far along \(\tilde{\pi}\) as \(w'\), so that we can reach \(w\) with a single edge. Consider the following two cases:
Case 1: If \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u_p) \ge \mathop{\mathrm{d}}_{\tilde{G}_i}(u,w')\), we define \(u' := u_p\).
Case 2: If \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u_p) < \mathop{\mathrm{d}}_{\tilde{G}_i}(u,w')\), we define \(u' := w'\).
Case 1. Suppose \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u_p) \ge \mathop{\mathrm{d}}_{\tilde{G}_i}(u,w')\). In this case, the vertex \(u_p\) already lies at or beyond \(w'\) along the path \(\tilde{\pi}\). We therefore have \(u' = u_p\) and define \(\pi_{\text{pre}} := \pi_i\), as illustrated in Figure 4. Thus, we have \(\mathop{\mathrm{w}}_H(\pi_{\text{pre}}) = \mathop{\mathrm{w}}_H(\pi_{i}) \le (1+\epsilon)^{i+1}(\alpha p + \beta)\) and \(|\pi_{\text{pre}}| = |\pi_i|\le \alpha (t+t\epsilon) + \beta = \alpha t + \alpha t\epsilon + \beta \le \alpha t + \alpha t \epsilon + t \epsilon \le 2t(\alpha + 1)\), since \(\beta \le t\epsilon\) and \(\epsilon \le 1\).
By comparing the weight of the path \(\pi_{\text{pre}}\) in \(H\) to the exact distance from \(u\) to \(u'\) in \(\tilde{G}_i\), we can bound the multiplicative stretch \(\lambda_1\) which the path \(\pi_{\text{pre}}\) introduces: \[\begin{align} \lambda_1 :=\frac{\mathop{\mathrm{w}}_H(\pi_{\text{pre}})}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')} &\le \frac{(1+\epsilon)^{i+1} (\alpha p +\beta)}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')}. \end{align}\] The vertex \(u'\) satisfies \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') \ge p (1+\epsilon)^i\) by construction of \(u_p\). Substituting this yields \[\begin{align} \lambda_1 = \frac{\mathop{\mathrm{w}}_H(\pi_{\text{pre}})}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')} &\le \frac{(1 + \epsilon)^{i+1} (\alpha p + \beta)}{p(1+\epsilon)^i} = \frac{(1+\epsilon)(\alpha p +\beta)}{p} = (1+\epsilon) \left(\alpha + \frac{\beta}{p}\right). \end{align}\]
Case 2. Suppose that \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u_p) < \mathop{\mathrm{d}}_{\tilde{G}_i}(u,w')\). In this situation, \(u_p\) lies strictly before \(w'\) along \(\tilde{\pi}\). We have defined \(u' = w'\) and to construct \(\pi_{\text{pre}}\), we extend the path \(\pi_i\) with an additional shortcut path from \(u_p\) to \(w'\), as shown in Figure 5. Since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w') < \Delta t\), the construction of \(u_p\) in Claim [claim:up] implies that the remaining distance from \(u_p\) to \(w'\) is \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,w') < (1+\epsilon)^i\).
Case 1. We first consider the trivial case where \(u_p = u\), thus \(\pi_i\) is the empty path. Since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,w') < (1+\epsilon)^i\), we know that there exists a smaller distance scale \(j < i\), such that \(\mathop{\mathrm{d}}_G(u,u')\) falls into this scale, i.e. \((1+\epsilon)^j \le \mathop{\mathrm{d}}_G(u,u') < (1+\epsilon)^{j+1}\). Hence, by definition, we have an edge from \(u\) to \(u'\) in the graph \(G_j\). Let \(\pi_\text{pre}\) be defined as the path from \(u\) to \(u'\) in \(H\) with \(\mathop{\mathrm{w}}_H(\pi_\text{pre}) \le (1+\epsilon)^{j+1} (\alpha +\beta)\) and \(|\pi_\text{pre}| = \alpha+\beta\), as provided by Claim [claim:weight95hop95emulatorpaths]. To bound the stretch of this shortcut, we compare the weight of \(\pi_{\text{pre}}\) to the exact distance between \(u\) and \(u'\) in \(G\). Since \((1+\epsilon)^j \le \mathop{\mathrm{d}}_G(u,u')\), this yields a stretch \(\lambda_{2.1}\) of \[\lambda_{2.1} := \frac{\mathop{\mathrm{w}}_H(\pi_{\text{pre}})}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')} \le \frac{(1+\epsilon)^{j+1}(\alpha +\beta)}{(1+\epsilon)^j} = (1+\epsilon)(\alpha + \beta).\]**
Case 2. Next, we consider the case where \(u \ne u_p\). Let \(x\) be the vertex in \(\mathop{\mathrm{origin}}(u_p)\) that succeeds \(u_p\) on \(\tilde{\pi}\), i.e., \(x\) is the first vertex in \(V\) on the subpath \(\tilde{\pi}[u_p,v]\).**
We construct the path \(\pi_\text{pre}\) by combining the path \(\pi_i\) from \(u\) to \(u_p\) with a path \(\pi_j\) from \(x\) to \(u'\). If \(u_p = x\), we can directly concatenate \(\pi_i\) and \(\pi_j\). Otherwise if \(u_p \neq x\), by definition, there exists an edge \((u_p,x) \in F\) with weight \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_p, x)\) and we extend \(\pi_i\) by \((u_p,x)\) before concatenating it with \(\pi_j\).
The definition of \(\pi_j\) is based on the following cases:
If \(x = u'\): Let \(\pi_j\) be the empty path.
If \(x \ne u'\): We know that the remaining distance from \(x\) to \(u'\) is \(\mathop{\mathrm{d}}_{\tilde{G}_i}(x,u') < (1+\epsilon)^i\), since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,x) \ge \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p)\) and \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u, u') -\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) < (1+\epsilon)^i\). Hence \(\mathop{\mathrm{d}}_{\tilde{G}_i}(x, u')\) falls into some distance scale \(j\) with \(j < i\) and since \(x, u' \in V\) there is, by definition, a single edge from \(x\) to \(u'\) in \(G_j\). Let \(\pi_j\) denote the path in \(H\) with \(\mathop{\mathrm{w}}_H(\pi_j) \le (1+\epsilon)^{j+1} (\alpha +\beta)\) from \(x\) to \(u'\), guaranteed by Claim [claim:weight95hop95emulatorpaths].
Thus the number of edges in \(\pi_\text{pre}\) is \(\pi_\text{pre} \le |\pi_i| + |\pi_j| + 1\). Its weight is \(\mathop{\mathrm{w}}_{H}(\pi_{\text{pre}}) \le \mathop{\mathrm{w}}_{H}(\pi_{i}) + \mathop{\mathrm{w}}_{H}(\pi_{j}) + \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p, x)\).
Using \(|\pi_i| \le \alpha (t+t\epsilon) + \beta\) and \(|\pi_j| \le \alpha + \beta\), the number of edges can be bounded as follows \[\begin{align} |\pi_{\text{pre}}| \le |\pi_i| +|\pi_j| + 1 &\le \alpha (t+t\epsilon) + \beta + \alpha +\beta + 1 = \alpha t + \alpha t\epsilon+\alpha +2\beta +1 \\ &\le \alpha t + \alpha t\epsilon + \alpha t + 2t\epsilon + t \le 3t(\alpha+1). \end{align}\]
To analyze the stretch of this shortcut, we compare the weight of \(\pi_\text{pre}\) to the exact distance from \(u\) to \(u'\) in \(\tilde{G}_i\). We know that, if present, the edge \((u_p, x)\) has weight \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_p, x)\), which does not contribute to the stretch of the shortcut path. Otherwise \(u_p = x\) and therefore \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x) = 0\). Hence, to obtain the stretch \(\lambda_{2.2}\), it suffices to bound the ratio \[\begin{align} \lambda_2 := \frac{\mathop{\mathrm{w}}_H(\pi_{\text{pre}}) - \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x)}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') - \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x)}. \end{align}\] Since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') - \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x)> \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p)\) and \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) > p(1+\epsilon)^i\), this yields: \[\begin{align} \lambda_{2.2} = \frac{\mathop{\mathrm{w}}_H(\pi_{\text{pre}}) - \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x)}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') - \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x)} &\le \frac{\mathop{\mathrm{w}}_H(\pi_i) + \mathop{\mathrm{w}}_H(\pi_j) + \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x) - \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x)}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') - \mathop{\mathrm{d}}_{\tilde{G}_i}(u_p,x)} \\ &\le \frac{\mathop{\mathrm{w}}_H(\pi_i) + \mathop{\mathrm{w}}_H(\pi_j) }{p(1+\epsilon)^i}. \end{align}\] Further since \(\mathop{\mathrm{w}}_H(\pi_i) \le (1+\epsilon)^{i+1} (\alpha p+ \beta)\) and \(\mathop{\mathrm{w}}_H(\pi_j) \le (1+\epsilon)^{j+1} (\alpha + \beta) < (1+\epsilon)^{i+1} (\alpha + \beta)\), we have \[\begin{align} \mathop{\mathrm{w}}_{H}(\pi_{i}) + \mathop{\mathrm{w}}_{H}(\pi_{j}) &\le (1+\epsilon)^{i+1}(\alpha p +\beta) + (1+\epsilon)^{i+1}(\alpha+\beta) = (1+\epsilon)^{i+1} (\alpha p + \alpha + 2 \beta). \end{align}\] This allows us to bound \(\lambda_{2.2}\) by \[\begin{align} \lambda_{2.2} &\le \frac{\mathop{\mathrm{w}}_H(\pi_i) + \mathop{\mathrm{w}}_H(\pi_j) }{p(1+\epsilon)^i} \le \frac{(1+\epsilon)^{i+1} (\alpha p + \alpha + 2 \beta) }{p(1+\epsilon)^i} \\ &= \frac{(1+\epsilon) (\alpha p + \alpha + 2 \beta) }{p} = (1+\epsilon) \left(\alpha + \frac{\alpha}{p}+2\frac{\beta}{p}\right). \end{align}\]
Having defined \(u'\) and \(\pi_\text{pre}\), it remains to show that we can reach the vertex \(w\) on \(\pi\) with a single edge from \(u'\) to \(w\).
If \(u'\ne w'\): This only occurs in Case 1 where \(u' = u_p\) and we have \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w') < \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p)\). Since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u_p) \le \Delta t \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)\), the vertex \(u_p\) must have been introduced during the subdivision of the edge \((w',w) \in E\). Therefore, in our construction, we have inserted the edge \((u', w)\) into \(\tilde{F}_i \subseteq F\), with weight \(\mathop{\mathrm{w}}_F((u', w)) = \delta(u', w) =\mathop{\mathrm{d}}_{\tilde{G}_i}(u',w)\).
If \(u' = w'\): This can occur in either Case 1 or Case 2. We simply take the edge \((u', w) = (w',w) \in E\).
Let \(\pi'\) be the path in \(H\) obtained by extending \(\pi_{\text{pre}}\) with the edge \((u',w) \in E\) or \((u',w) \in F\), as illustrated in Figure 6.
We have previously shown that in all cases \(|\pi_{\text{pre}}| \le 3t(\alpha+1)\). Thus the path \(|\pi'|\) consists of at most \(3t(\alpha+1) + 1\) edges as claimed. Depending on the case, we showed that \(\mathop{\mathrm{w}}_H(\pi_{\text{pre}}) \le \lambda \cdot \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')\) for \(\lambda \in \{\lambda_1,\lambda_{2.1},\lambda_{2.2}\}\). Since the last edge \((u',w)\) of the path \(\pi\) is exact, it introduces no additional error, and the weight of \(\pi'\) can be expressed as \[\begin{align} \mathop{\mathrm{w}}_H(\pi') &= \mathop{\mathrm{w}}_H(\pi_{\text{pre}}) + \mathop{\mathrm{w}}_H((u', w)) \le \lambda \cdot \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') + \mathop{\mathrm{d}}_{\tilde{G}_i}(u',w) \\ &= \lambda \cdot \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') + (\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w) - \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')) = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,w) + (\lambda - 1) \cdot \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u'). \end{align}\] This allows us to bound the stretch of \(\pi'\) by comparing its weight to the exact distance from \(u\) to \(w\) in \(\tilde{G}_i\) (which coincides with the distance in \(G\)). Since \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w) \ge \Delta t \ge t (1+\epsilon)^i\), we obtain the following: \[\frac{\mathop{\mathrm{w}}_H(\pi')}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)} \le \frac{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w) + (\lambda - 1) \cdot \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)} \le 1 + \left( \lambda - 1 \right) \frac{ \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)} \le 1 + \left( \lambda - 1 \right) \frac{ \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')}{t (1+\epsilon)^i}\]
Now, it remains to show that in all cases (Case 1, 1 and 2) for the corresponding \(\lambda\) and an appropriate upper bound for \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')\), we can bound the stretch of \(\pi'\) with \(\alpha(1 + 24 \epsilon)\).
First, we consider the simple Case 1. Here we derived the stretch \(\lambda_{2.1} = (1+\epsilon)(\alpha+\beta)\) for the path \(\pi_{\text{pre}}\). Because in this case, we have \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') < (1+\epsilon)^{i}\), the stretch of \(\pi'\) can be bounded as follows \[\begin{align} \frac{\mathop{\mathrm{w}}_H(\pi')}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)} &\le 1 + \left( (\lambda_{2.1} - 1 \right) \frac{(1+\epsilon)^i}{t(1+\epsilon)^i} \le 1 + \left( (1+\epsilon) (\alpha+\beta) - 1 \right) \frac{(1+\epsilon)^i}{t(1+\epsilon)^i} \\ &= 1 + \left( (1+\epsilon)\alpha + (1+\epsilon)\beta - 1 \right) \frac{1}{t} = 1 + \left( (1+\epsilon)\alpha - 1 \right) \frac{1}{t} + (1+\epsilon)\beta \frac{1}{t} \\ \end{align}\] As \(t = \max(\frac{1}{\epsilon},\frac{\beta}{\epsilon})\), we have \(\frac{1}{t} \le \epsilon \le 1\) and \(\frac{\beta}{t} \le \epsilon\). This yields \[\begin{align} \frac{\mathop{\mathrm{w}}_H(\pi')}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)} &\le 1 + (1+\epsilon)\alpha - 1 + (1+\epsilon) \epsilon = \alpha + \alpha \epsilon + \epsilon +\epsilon^2 \le \alpha (1+\epsilon + \epsilon +\epsilon^2) \\&\le \alpha(1+3\epsilon). \end{align}\]
Next, we examine the remaining cases. In Case 1 we know that \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') \le p (1+\epsilon)^{i+1}\) and derived the stretch \(\lambda_1 = (1+\epsilon)(\alpha+\frac{\beta}{p})\). In Case 2 we have \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') \le p (1+\epsilon)^{i+1} + (1+\epsilon)^i\) and the stretch \(\lambda_{2.2} = (1+\epsilon)(\alpha + \frac{\alpha}{p} + 2 \frac{\beta}{p})\). Since \(\lambda_{2.2} > \lambda_1\) and \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')\) in Case 2 is larger than in Case 1, we can bound the stretch of \(\pi'\) for these cases as follows: \[\begin{align} \frac{\mathop{\mathrm{w}}_H(\pi')}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)} &\le 1 + \left( \lambda_{1} - 1 \right) \frac{ p(1+\epsilon)^{i+1}}{t (1+\epsilon)^i} \le 1+(\lambda_{2.2} - 1) \frac{p(1+\epsilon)^{i+1}+(1+\epsilon)^i}{t(1+\epsilon)^i}\\ &= 1+(\lambda_{2.2} - 1) \left(\frac{p}{t}(1+\epsilon) + \frac{1}{t}\right)= 1+(\lambda_{2.2}- 1) \frac{p}{t}(1+\epsilon) + (\lambda_{2.2} - 1) \frac{1}{t}. \end{align}\] The term \((\lambda_2 - 1) \frac{p}{t}(1+\epsilon)\), can be expressed as \[\begin{align} (\lambda_2 - 1) \frac{p}{t}(1+\epsilon)&= \left((1+\epsilon)(\alpha+\frac{\alpha}{p}+2\frac{\beta}{p} )-1\right)\frac{p}{t}(1+\epsilon) \\ &= \left(\alpha(1+\epsilon) + \frac{\alpha}{p}(1+\epsilon)+2\frac{\beta}{p}(1+\epsilon)-1\right)\frac{p}{t}(1+\epsilon) \\ &= (\alpha(1+\epsilon) - 1) \frac{p}{t} (1+\epsilon) + \frac{\alpha}{p}\frac{p}{t}(1+\epsilon)^2+2\frac{\beta}{p}\frac{p}{t}(1+\epsilon)^2. \end{align}\] Given that \(\frac{p}{t} \le \frac{t+t\epsilon}{t} = 1+\epsilon\), \(\frac{\alpha}{p}\frac{p}{t} \le \alpha \epsilon\) and \(\frac{\beta}{p}\frac{p}{t} \le \epsilon\), we get \[\begin{align} (\lambda_2 - 1) \frac{p}{t}(1+\epsilon) &\le (\alpha(1+\epsilon) - 1) (1+\epsilon)^2 +\alpha \epsilon (1+\epsilon)^2+2\epsilon(1+\epsilon)^2\\ &= \alpha(1+\epsilon)^3 - (1+\epsilon)^2 +\alpha \epsilon (1+\epsilon)^2+2\epsilon(1+\epsilon)^2\\ &= \alpha(1+\epsilon)^3 - 1 - 2\epsilon -\epsilon^2 +\alpha \epsilon (1+\epsilon)^2+2\epsilon+4\epsilon^2+2\epsilon^3\\ &= - 1+\alpha(1+\epsilon)^3 +\alpha \epsilon (1+\epsilon)^2+3\epsilon^2+2\epsilon^3. \end{align}\] Since \(\frac{1}{p} \le 1\), \(\frac{\beta}{t} \le \epsilon\) and \(\frac{1}{t} \le \epsilon\), the term \((\lambda_2 - 1) \frac{1}{t}\) is bounded by \[\begin{align} (\lambda_2 - 1) \frac{1}{t} &\le \lambda_2 \frac{1}{t} = (1+\epsilon)\left(\alpha+\frac{\alpha}{p}+2\frac{\beta}{p} \right) \frac{1}{t} \\ &\le (1+\epsilon)(2\alpha + 2\beta) \frac{1}{t}= (1+\epsilon) \left(2\alpha\frac{1}{t} + 2\frac{\beta}{t}\right) \\ &\le (1+\epsilon) (2\alpha\epsilon + 2\epsilon) = 2\alpha\epsilon + 2\epsilon + 2\alpha\epsilon^2 +2\epsilon^2. \end{align}\] Using these two bounds, we obtain \[\begin{align} \frac{\mathop{\mathrm{w}}_H(\pi')}{\mathop{\mathrm{d}}_{\tilde{G}_i}(u,w)} &\le 1+(\lambda_2 - 1) \frac{p}{t}(1+\epsilon) + (\lambda_2 - 1) \frac{1}{t} \\ &\le 1 - 1+\alpha(1+\epsilon)^3 +\alpha \epsilon (1+\epsilon)^2+3\epsilon^2+2\epsilon^3 + 2\alpha\epsilon + 2\epsilon + 2\alpha\epsilon^2 +2\epsilon^2 \\ &\le \alpha \left((1+\epsilon)^3 + \epsilon(1+\epsilon)^2+4\epsilon+7\epsilon^2+2\epsilon^3\right)\\ &= \alpha \left(1+3\epsilon + 3\epsilon^2 + \epsilon^3 + \epsilon + 2\epsilon^2 + \epsilon^3 +4\epsilon+7\epsilon^2+2\epsilon^3\right) \\ &\le \alpha (1+24\epsilon). \end{align}\] Hence, the path \(\pi'\) achieves the claimed stretch of at most \(\alpha(1 + 24 \epsilon)\) in all cases. ◻
By repeatedly applying the shortcuts of Lemma 3 and concatenating them, we construct the alternative path \(\pi''\) to get the following Lemma.
Lemma 4. For every pair of vertices \(u,v \in V\) with \(\mathop{\mathrm{d}}_G(u,v) < \infty\), there exists a path \(\pi''\) from \(u\) to \(v\) in the graph \(H = (V', E \cup F)\), which consists of at most \((3t^2 (\alpha +1) + t)\ln(nW)\) edges, and has weight \(\mathop{\mathrm{w}}_H(\pi'') \le \alpha(1+24\epsilon) \cdot \mathop{\mathrm{d}}_G(u,v)\).
Proof. Let \(\pi\) be the shortest path between \(u\) and \(v\) in \(G\). The goal is to find a sequence of vertices \(w_0,w_1,\dots,w_k\) on \(\pi\) and a sequence of alternative paths \(\pi'_0, \pi'_1,\dots,\pi_{k-1}'\), where each \(\pi'_i \in H\) is a path from \(w_i\) to \(w_{i+1}\). Let \(\pi''\) denote the path obtained by concatenating all paths \(\pi_i'\). Let \(w_0 = u\) and let \(w_i\) for \(1\le i \le k\) be the vertex on \(\pi\), found as described in Lemma 3, with \(k\) chosen such that \(w_k = v\), and \(\Delta\) defined as \(\Delta = \frac{\mathop{\mathrm{d}}_G(w_i,v)}{t^2}\) in order to find the vertex \(w_{i+1}\).
From Lemma 3, we know that each alternative path \(\pi'_i\) has at most \(3t(\alpha +1) + 1\) hops. Thus, the concatenation of all alternative paths consists of at most \(k (3t(\alpha +1) + 1)\) edges. Likewise, Lemma 3 ensures that when using a shortcut \(\pi_i'\) we skip a distance of \(\Delta t = \frac{\mathop{\mathrm{d}}_G(w_i,v)}{t^2}t = \frac{\mathop{\mathrm{d}}_G(w_i,v)}{t}\), and we know that the remaining distance is: \[\mathop{\mathrm{d}}_G(w_{i+1}, v) \le \mathop{\mathrm{d}}_G(w_i, v) - \frac{\mathop{\mathrm{d}}_G(w_i, v)}{t} = \left(1-\frac{1}{t}\right)\mathop{\mathrm{d}}_G(w_i,v).\] Further, we can say that for every \(0\le i \le k\): \[\begin{align} \mathop{\mathrm{d}}_G(w_i, v) \le \left(1-\frac{1}{t}\right)\mathop{\mathrm{d}}_G(w_{i-1}, v) \le \left(1-\frac{1}{t}\right)\left(1-\frac{1}{t}\right)\mathop{\mathrm{d}}_G(w_{i-2},v) \le \dots \le \left(1-\frac{1}{t}\right)^i \mathop{\mathrm{d}}_G(u,v) . \end{align}\]
To analyze how many of such shortcuts are needed in order to reach \(v\), we need to determine for which \(k\) it is ensured that the remaining distance satisfies \(\mathop{\mathrm{d}}_G(w_k,v) \le (1-\frac{1}{t})^k \mathop{\mathrm{d}}_G(u,v) < 1\). Since \(\mathop{\mathrm{d}}_G(u,v) \le (n-1)W < nW\), it follows that \[\begin{align} 1 &>\frac{1}{nW} \mathop{\mathrm{d}}_G(u,v) = \left(\frac{1}{e}\right)^{\ln(nW)} \mathop{\mathrm{d}}_G(u,v). \end{align}\] Noting that \((1-\frac{1}{t})^t \le \frac{1}{e}\), this yields \[\begin{align} \left(\frac{1}{e}\right)^{\ln(nW)} \mathop{\mathrm{d}}_G(u,v) &\ge \left(1-\frac{1}{t}\right)^{t \cdot \ln(nW)}\mathop{\mathrm{d}}_G(u,v). \end{align}\] Thus \(\mathop{\mathrm{d}}_G(w_k,v) < 1\) holds, for every \(k \ge t \cdot \ln(nW)\). Therefore the path \(\pi''\) contains at most \(k(3t(\alpha+1) + 1)=\ln(nW) t (t (\alpha+1) + 1) = \ln(nW)(3t^2(\alpha +1) + t)\) many edges.
We can bound the weight of the path \(\pi''\) by \(\mathop{\mathrm{w}}_H(\pi'') \le \alpha (1+24\epsilon) \cdot \mathop{\mathrm{d}}_G(u,v)\) as follows. Since Lemma 3 guarantees that each alternative path \(\pi_i'\) has weight \(\mathop{\mathrm{w}}_H(\pi'_i) \le \alpha (1+24\epsilon) \cdot \mathop{\mathrm{d}}_G(w_i,w_{i+1})\), and all \(w_i\) lie on the shortest path between \(u\) and \(v\) we have: \[\begin{align} \mathop{\mathrm{w}}_H(\pi'') = \sum_{i = 0}^{k-1} \mathop{\mathrm{w}}_H(\pi_i') &\le \sum_{i = 0}^{k-1} \alpha (1+24\epsilon) \cdot \mathop{\mathrm{d}}_G(w_i,w_{i+1}) \\ &= \alpha (1+24\epsilon) \cdot \sum_{i = 0}^{k-1}\mathop{\mathrm{d}}_G(w_i,w_{i+1}) = \alpha (1+24\epsilon) \cdot \mathop{\mathrm{d}}_G(u,v). \qedhere \end{align}\] ◻
2.4 Projection to the Original Vertex Set↩︎
So far, we have shown that the edge set \(F \subseteq V' \times V'\) as constructed in Section 2.1 is a \(V\)-constrained hopset of the extended graph \(G' = (V',E)\). However, our goal is to obtain a hopset for the original graph \(G=(V,E)\), which consists solely of edges between original vertices \(V\). Let \(V_{\text{sub}} := V'\setminus V\) be the set of the subdivision vertices. In this section, we describe how to project \(F\) to a hopset \(F_R \subseteq V^2\) that preserves the same stretch and hopbound guarantees. Recall Definition [def:origin] and Definition [def:delta] for a vertex in \(V' = \bigcup_{i=0}^{i_{\text{max}}} \tilde{V}_i\).
Intuitively, the subdivision vertices represent specific points on the original edges, and the respective \(\delta\) values denote their exact positions relative to the endpoints of the edge. Therefore, our strategy with the projection is that whenever an edge in the hopset \(F\) is incident to at least one vertex in \(V_{\text{sub}}\), we shift it to the nearby original vertices in \(V\) (illustrated in Figure 7), while adjusting the weight using the corresponding \(\delta\) value. This shift is realized by replacing a single edge in \(F\) with up to four new edges and can be formalized as a function \(\phi :F \to \mathcal{P}(V^2)\). For any edge \(e = (u,v) \in F\): \[\phi(e) := \begin{cases} \mathop{\mathrm{origin}}(u) \times \mathop{\mathrm{origin}}(v) & \text{if } \mathop{\mathrm{origin}}(u) \cap \mathop{\mathrm{origin}}(v) = \emptyset\\[4pt] \emptyset & \text{otherwise.} \end{cases}\]
Before we define the weights of the projected edges, we first introduce the notion of the signed offset \(\eta_{u,v}\).
Definition 5 (Signed Offset). Let \(e = (u,v) \in F\), and let \(\pi\) be a shortest path from \(u\) to \(v\) in \(\tilde{G}_i\). For \(s \in \{u,v\}\) and \(t \in \mathop{\mathrm{origin}}(s)\), the signed offset is defined as follows \[\begin{align} \eta_{u,v}(s,t) := \begin{cases} - \delta(s,t) & \text{if t is the first vertex in \mathop{\mathrm{origin}}(s) encountered when traversing \pi starting from s} \\ + \delta(s,t) & \text{otherwise.} \end{cases} \end{align}\] Note, if \(\mathop{\mathrm{origin}}(s) = \{s\}\) then \(\delta(s,s) = 0\).
Using this signed offset, the weight of an edge \((x,y) \in \phi(e)\) is given by \[\begin{align} \mathop{\mathrm{w}}_{\phi(e)}((x,y)) &:= \mathop{\mathrm{w}}_{F}((u,v)) + \eta_{u,v}(u,x) + \eta_{u,v}(v,y). \end{align}\] We define the set of edges \(F_R\subseteq V \times V\) as \[F_{R} := \bigcup_{e\in F}\quad \phi(e).\] Finally, for each edge \(f \in F_R\), its weight is defined as \[\mathop{\mathrm{w}}_{F_R}(f) := \min(\mathop{\mathrm{w}}_{\phi(e)}(f) \mid e \in F \wedge f \in \phi(e)).\]
We will now show that \(F_R\) forms a hopset. First, we will prove that the weights assigned to the edges in \(F_R\) do not underestimate the original distances. To achieve this, we first establish two properties regarding the relationship between vertices and their origin.
Consider a distance scale \(i \ge 0\). Let \(u,v \in \tilde{V}_i\) with \(\mathop{\mathrm{origin}}(u) \cap \mathop{\mathrm{origin}}(v) = \emptyset\) and let \(\pi\) be any path between \(u\) and \(v\) in \(\tilde{G}_i\). There exist vertices \(u' \in \mathop{\mathrm{origin}}(u)\) and \(v' \in \mathop{\mathrm{origin}}(v)\) that lie on \(\pi\). Furthermore, the subpaths of \(\pi\) from \(u\) to \(u'\) and \(v\) to \(v'\) are vertex disjoint, and have weights \(\delta(u,u')\) and \(\delta(v,v')\), respectively.
Proof. Let \(\pi\) be any path from \(u\) to \(v\) in \(\tilde{G}_i\) and let \(s \in \{u,v\}\).
Case 3. \(s \in V\). Then \(\mathop{\mathrm{origin}}(s) = \{s\}\), so the subpath \(\pi[s,s]\) is trivial with weight \(0 = \delta(s,s)\).
Case 4. \(s \in \tilde{V}_i \setminus V\). Let \(\mathop{\mathrm{origin}}(s) = \{s',s''\}\). By definition of \(\mathop{\mathrm{origin}}(s)\) and \(\tilde{G}_i\), the vertex \(s\) lies on the subdivision path connecting \(s'\) and \(s''\), whose internal vertices all have degree two. Thus, any path from \(s\) to a vertex outside this subdivision path, i.e., with a different \(\mathop{\mathrm{origin}}\), must contain at least one of \(s'\) or \(s''\). Let \(s'\) be the first of these two vertices encountered when traversing \(\pi\) starting from \(s\). By definition, the weight of the path from \(s\) to \(s'\) along this subdivision path is \(\delta(s,s')\), as claimed.
Let \(u'\) and \(v'\) be the vertices identified for \(u\) and \(v\), respectively. Since \(\mathop{\mathrm{origin}}(u)\cap\mathop{\mathrm{origin}}(v)=\emptyset\), the subpaths \(\pi[u,u']\) and \(\pi[v',v]\) are vertex disjoint. ◻
Consider a distance scale \(i \ge 0\). For every pair of vertices \(u,v \in \tilde{V}_i\) with \(\mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) < \infty\) and \(\mathop{\mathrm{origin}}(u) \cap\mathop{\mathrm{origin}}(v) = \emptyset\) and for any \(x \in \mathop{\mathrm{origin}}(u)\) and \(y \in \mathop{\mathrm{origin}}(v)\), the following holds \(\mathop{\mathrm{d}}_{\tilde{G}_i}(x,y) \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,x)+\eta_{u,v}(v,y)\).
Proof. Let \(\pi\) be a shortest path between \(u\) and \(v\) in \(\tilde{G}_i\). We consider three cases.
Case 5. \(u,v \in V\). We have \(\mathop{\mathrm{origin}}(u) = \{u\}\) and \(\mathop{\mathrm{origin}}(v) = \{v\}\). By definition, \(\delta(u,u) = \delta(v,v) = 0\) and \(\eta_{u,v}(u,u) = \eta_{u,v}(v,v) = 0\). Hence, \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v)= \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,u)+\eta_{u,v}(v,v). \end{align}\]
Case 6. \(u \in V\) and \(v \in \tilde{V}_i\setminus V\). Here \(\mathop{\mathrm{origin}}(u) = \{u\}\) and let \(\mathop{\mathrm{origin}}(v) = \{v',v''\}\), where \(v'\) is the vertex on \(\pi\) guaranteed by Observation [obs:origin-contained-in-every-path]. Since \(\pi\) is a shortest path, we have \(\delta(v,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v')\), and since \(v'\) lies on \(\pi\), the following holds \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \delta(v,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(v,v'). \end{align}\] For \(v''\), we use the triangle inequality and the fact that \(\mathop{\mathrm{d}}_{\tilde{G}_i}(v,v'') \le \delta(v,v'')\), to obtain \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v'') \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v'') \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \delta(v,v'') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(v,v''). \end{align}\]
Case 7. \(u,v \in \tilde{V}_i\setminus V\). Let \(\mathop{\mathrm{origin}}(u) = \{u',u''\}\) and \(\mathop{\mathrm{origin}}(v) = \{v',v''\}\), where \(u'\) and \(v'\) are the vertices on \(\pi\) guaranteed by Observation [obs:origin-contained-in-every-path]. Again since \(\pi\) is a shortest path, we have \(\delta(u,u') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u')\) and \(\delta(v,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v')\). Since \(u'\) and \(v'\) lie on \(\pi\) and the subpaths \(\pi[u,u']\) and \(\pi[v',v]\) are vertex-disjoint, the distance between them is \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') - \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \delta(u,u') - \delta(v,v'). \end{align}\] By definition of \(\eta_{u,v}\), we get \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v') =\mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,u') + \eta_{u,v}(v,v'). \end{align}\] Similarly the distances from \(u\) to \(v'\) and \(v\) to \(u'\) are: \[\label{equa:path-decomp} \begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v') &= \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \delta(v,v') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(v,v') \\ \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v) &= \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) - \delta(u,u') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,u'). \end{align}\qquad{(1)}\] For the remaining vertex pairs in \(\mathop{\mathrm{origin}}(u) \times \mathop{\mathrm{origin}}(v)\) using the triangle inequality, yields \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v'') &\le \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v) + \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v'') \\ \mathop{\mathrm{d}}_{\tilde{G}_i}(u'',v') &\le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v') + \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u'') \\ \mathop{\mathrm{d}}_{\tilde{G}_i}(u'',v'') &\le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \mathop{\mathrm{d}}_{\tilde{G}_i}(u,u'') + \mathop{\mathrm{d}}_{\tilde{G}_i}(v,v''). \end{align}\] Combining Eq. ?? , the bound \(\delta(s,t) \ge \mathop{\mathrm{d}}_{\tilde{G}_i}(s,t)\) for \(s \in \{u,v\}\) and \(t \in \mathop{\mathrm{origin}}(s)\), and the definition of \(\eta_{u,v}\), we obtain \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v'') &\le \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v) + \delta(v,v'') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u',v) + \eta_{u,v}(v,v'') =\mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,u') + \eta_{u,v}(v,v'') \\ \mathop{\mathrm{d}}_{\tilde{G}_i}(u'',v') &\le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v') + \delta(u,u'') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v') + \eta_{u,v}(u,u'') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,u'') + \eta_{u,v}(v,v')\\ \mathop{\mathrm{d}}_{\tilde{G}_i}(u'',v'') &\le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \delta(u,u'') + \delta(v,v'') = \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,u'') + \eta_{u,v}(v,v''). \end{align}\]
Therefore in all cases, the distance between \(x \in \mathop{\mathrm{origin}}(u)\) and \(y \in \mathop{\mathrm{origin}}(v)\) can be stated as \[\mathop{\mathrm{d}}_{\tilde{G}_i}(x,y) \le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,x)+\eta_{u,v}(v,y). \qedhere\] ◻
Using Claim [claim:distance-upperbound], we now show that each edge in \(F_R\) has weight at least the corresponding distance in \(G\).
Lemma 5. For every edge \((x,y) \in F_R\), its assigned weight satisfies \(\mathop{\mathrm{w}}_{F_R}((x,y)) \ge \mathop{\mathrm{d}}_G(x,y)\).
Proof. Consider an edge \(e = (u,v) \in F\) and let \((x,y) \in \phi(e)\). Let \(i\) be any distance scale \((u,v)\) belongs to, i.e., \((u,v)\) appears in the emulator \(M_i\). The construction of \(F\) ensures that \(\mathop{\mathrm{w}}_F((u,v)) \ge \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v)\) holds. By definition, \[\begin{align} \mathop{\mathrm{w}}_{\phi(e)}((x,y)) &= \mathop{\mathrm{w}}_{F}((u,v)) + \eta_{u,v}(u,x) + \eta_{u,v}(v,y). \end{align}\] From Claim [claim:distance-upperbound], we know that the distance between \(x\) and \(y\) in \(\tilde{G}_i\) satisfies \[\begin{align} \mathop{\mathrm{d}}_{\tilde{G}_i}(x,y) &\le \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,x) + \eta_{u,v}(v,y). \end{align}\] Now it is easy to see that \[\begin{align} \mathop{\mathrm{w}}_{\phi(e)}(x,y) &= \mathop{\mathrm{w}}_{F}((u,v)) + \eta_{u,v}(u,x) + \eta_{u,v}(v,y) \\ &\ge \mathop{\mathrm{d}}_{\tilde{G}_i}(u,v) + \eta_{u,v}(u,x) + \eta_{u,v}(v,y) \\ &\ge \mathop{\mathrm{d}}_{\tilde{G}_i}(x,y) \\ &= \mathop{\mathrm{d}}_G(x,y). \end{align}\] Since \(F_R = \bigcup_{e\in F} \phi(e)\) and \(\mathop{\mathrm{w}}_{F_R}((x,y))\) is the minimum over all such projections, the Lemma follows. ◻
Next, we show that \(F_R\) preserves the same stretch and hopbound guarantees as \(F\). In particular, we show that any path in \(H = (V', E\cup F)\) can be simulated by a path in the graph \(H_R = (V, E \cup F_R)\) with no increase in weight or hop-count.
Lemma 6. For any pair of vertices \(u,v \in V\) and any path \(\pi\) from \(u\) to \(v\) in \(H = (V', E\cup F)\), there exists a path \(\pi_R\) in \(H_R = (V, E \cup F_R)\), such that \(\mathop{\mathrm{w}}_{H_R}(\pi_R) \le \mathop{\mathrm{w}}_H(\pi)\) and \(|\pi_R| \le |\pi|\).
Proof. Let \(\pi = (u = x_0,x_1,\dots, x_L = v)\) be a path between \(u\) and \(v\) in \(H\). We construct a path \(\pi_R = (u = y_0, y_1,\dots,y_{k(L)} = v)\) from \(u\) to \(v\) in \(H_R\) iteratively. For each \(0 \le l \le L\), let \(k(l)\) denote the index of the last vertex of \(\pi_R\) after processing the prefix \((x_0,\dots,x_l)\) of \(\pi\).
Let \(k(0) := 0\) and \(y_{k(0)} := x_0 = u\). Suppose that for some \(0 \le l < L\), we have already constructed the sequence \((y_0,y_1,\dots,y_{k(l)})\). For the next vertex \(x_{l+1}\) there are the following two cases:
\(y_{k(l)} \in \mathop{\mathrm{origin}}(x_{l+1})\). We set \(k(l+1):= k(l)\) and do not extend the sequence \((y_0,y_1,\dots,y_{k(l)})\).
\(y_{k(l)} \notin \mathop{\mathrm{origin}}(x_{l+1})\). In this case we set \(k(l+1):= k(l)+ 1\) and extend the sequence of vertices \((y_0,y_1,\dots,y_{k(l)})\), with a vertex \(y_{k(l+1)} \in \mathop{\mathrm{origin}}(x_{l+1})\). Specifically:
If \(x_{l+1} \in V\), then \(\mathop{\mathrm{origin}}(x_{l+1}) = \{x_{l+1}\}\), therefore \(y_{k(l+1)} = x_{l+1}\).
If \(x_{l+1} \in V_{\text{sub}}\), then let \(\mathop{\mathrm{origin}}(x_{l+1}) = \{x', x''\}\). We choose \(y_{k(l+1)} := x'\) , where \(x'\) denotes the vertex on the shortest path from \(x_l\) to \(x_{l+1}\) in the subdivision graph \(\tilde{G_i}\) guaranteed by Observation [obs:origin-contained-in-every-path], where \(i\) is the distance scale in which \(x_{l+1}\) was created.
Intuitively, in [item:yk95in95origin] the path \(\pi\) remains on the same original edge of \(G\), i.e., the vertices \(x_l\) and \(x_{l+1}\) are both part of the same subdivision of some edge \(E\). Taking the edge \((x_l,x_{l+1})\) does not move us closer to \(v\) in terms of original vertices. Whereas in [item:yk95notin95origin], the edge \((x_l,x_{l+1})\), allows us to advance to \(v\), by at least one original vertex of \(G\). An example illustration is given in Figure 8.
Continuing this process until \(x_{l+1} = x_L = v\) yields a path \(\pi_R = (y_0,y_1,\dots, y_{k(L)})\) in \(H_R\). Since by construction \(k(L) \le L\), we have \(|\pi_R| \le |\pi|\).
It remains to show that the sequence of vertices \(\pi_R\) is indeed a path in \(H_R\) and that its weight satisfies \(\mathop{\mathrm{w}}_{H_R}(\pi_R) \le \mathop{\mathrm{w}}_H(\pi)\). We do this by induction on \(l\): we will show, that for any \(0 \le l < L\), the sequence \((y_0,\dots,y_{k(l)})\) is a path in \(H_R\), that \(y_{k(l)} \in \mathop{\mathrm{origin}}(x_l)\) and \[\sum_{i = 0}^{l-1} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) \ge \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l)}, x_l).\] This implies that for the last vertex, for which \(x_L = v = y_{k(L)}\) and thus \(\delta(y_{k(L)}, x_L) = 0\) holds, that we have \[\begin{align} \mathop{\mathrm{w}}_H(\pi) = \sum_{i = 0}^{L-1} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) \ge \sum_{i = 0}^{k(L)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(L)}, x_L) = \sum_{i = 0}^{K-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) = \mathop{\mathrm{w}}_{H_R}(\pi_R). \end{align}\]
Base Case. For \(l=0\), we have \(k(l)=0\). The sequence \((y_0)\) is the trivial path. And since \(x_0 = y_0 \in
V\), \(y_0 \in \mathop{\mathrm{origin}}(x_0)\) holds by definition.
Induction Step. Suppose that for some \(0 \le l < L\), the sequence \((y_0,\dots,y_{k(l)})\) is a path in \(H_R\), that \(y_{k(l)} \in \mathop{\mathrm{origin}}(x_l)\) and that the following holds \[\sum_{i = 0}^{l-1} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) \ge \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) +
\delta(y_{k(l)}, x_l). \] Now consider the next vertex \(x_{l+1}\) on \(\pi\), we distinguish the same cases as in the construction of \(\pi_R\).
Case 8. \(y_{k(l)} \in \mathop{\mathrm{origin}}(x_{l+1})\).
In this case the sequence \((y_0,y_1\dots ,y_{k(l)})\) remained unchanged and we have \(k(l+1)= k(l)\), thus \(y_{k(l+1)} \in
\mathop{\mathrm{origin}}(x_{l+1})\) holds. We know that \[\mathop{\mathrm{w}}_H((x_l,x_{l+1})) \ge \delta(y_{k(l)}, x_{l+1}) - \delta(y_{k(l)},x_l) \] holds. This yields \[\begin{align}
\sum_{i = 0}^{l} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) &= \sum_{i = 0}^{l-1} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) \\ &\mathrel{\overset{\text{(IH)}}{\ge}} \sum_{i = 0}^{k(l)-1}
\mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l)}, x_l) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) \\ &\mathrel{\overset{\text{(a)}}{\ge}} \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l)}, x_{l+1}) \\ &= \sum_{i
= 0}^{k(l+1)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l+1)}, x_{l+1}).
\end{align}\] where the last equality holds, since we have \(k(l+1)= k(l)\).
Case 9. \(y_{k(l)} \notin \mathop{\mathrm{origin}}(x_{l+1})\).
According to the construction, the sequence \((y_0,y_1,\dots,y_{k(l)})\) is extended by a new vertex \(y_{k(l+1)}\) and \(k(l+1)= k(l)+1\).
Case 3. \(x_{l+1} \in V\). We chose \(y_{k(l+1)} = x_{l+1}\), since \(x_{l+1} \in V\) we have \(y_{k(l+1)} \in \mathop{\mathrm{origin}}(x_{l+1})\) by definition. The edge \((y_{k(l)}, x_{l+1})\) exists in \(E \cup F_R\), since**
If \((y_{k(l)}, x_{l+1}) \in E \cup F\), we consider the following
If \((y_{k(l)}, x_{l+1}) \in E\), then it is also in \(E \cup F_R\).
If \((y_{k(l)}, x_{l+1}) \in F\), we have \(\phi((y_{k(l)}, x_{l+1})) = \{(y_{k(l)}, x_{l+1})\}\) since both endpoints are in \(V\). Therefore \((y_{k(l)}, x_{l+1}) \in F_R\).
The weight of the edge is \(\mathop{\mathrm{w}}_{H_R}((y_{k(l)}, x_{l+1})) = \mathop{\mathrm{w}}_H((y_{k(l)},x_{l+1})) \le \delta(y_{k(l)}, x_l) + \mathop{\mathrm{w}}_{H}((x_l,x_{l+1}))\).
If \((y_{k(l)}, x_{l+1}) \notin E \cup F\). Since \(\mathop{\mathrm{origin}}(x_{l+1}) = \{x_{l+1}\}\) and \(y_{k(l)} \notin \mathop{\mathrm{origin}}(x_{l+1})\), we know that \(\mathop{\mathrm{origin}}(x_l)\cap\mathop{\mathrm{origin}}(x_{l+1})=\emptyset\) holds. Therefore we added \(\phi((x_l, x_{l+1})) = \mathop{\mathrm{origin}}(x_l) \times \mathop{\mathrm{origin}}(x_{l+1})\) to \(F_R\). Since \(y_{k(l)} \in \mathop{\mathrm{origin}}(x_l)\) is guaranteed by the induction hypothesis, we have \((y_{k(l)}, x_{l+1}) \in F_R\). Its weight is given by \(\mathop{\mathrm{w}}_{H_R}((y_{k(l)},x_{l+1})) \le \mathop{\mathrm{w}}_{\phi((x_l,x_{l+1}))}((y_k,x_{l+1})) = \delta(y_{k(l)}, x_l) + \mathop{\mathrm{w}}_{H}((x_l,x_{l+1}))\).
In either case, the sequence \((y_0,y_1,\dots, y_{k(l)},y_{k(l+1)})\) forms a path in \(H_R\). Moreover the weight of the edge \((y_{k(l)},y_{k(l+1)}) = (y_{k(l)},x_{l+1})\), satisfies \[\mathop{\mathrm{w}}_{H}((x_l,x_{l+1})) \ge \mathop{\mathrm{w}}_{H_R}((y_{k(l)},y_{k(l+1)})) - \delta(y_{k(l)}, x_l). \] Consequently, we obtain \[\begin{align} \sum_{i = 0}^{l} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) &= \sum_{i = 0}^{l-1} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) \\ &\mathrel{\overset{\text{(IH)}}{\ge}} \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l)}, x_l) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) \\ &\mathrel{\overset{\text{(b)}}{\ge}} \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l)}, x_l) + \mathop{\mathrm{w}}_{H_R}((y_{k(l)},y_{k(l+1)})) - \delta(y_{k(l)}, x_l) \\ &= \sum_{i = 0}^{k(l)} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) = \sum_{i = 0}^{k(l+1)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})), \end{align}\] where the final equality follows from \(k(l+1)= k(l)+1\). Since \(y_{k(l+1)} = x_{l+1}\), we have \(\delta(y_{k(l+1)}, x_{l+1}) = 0\), which yields \[\begin{align} \sum_{i = 0}^{l} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) \ge \sum_{i = 0}^{k(l+1)- 1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l+1)}, x_{l+1}). \end{align}\]
Case 4. \(x_{l+1} \in V_{\text{sub}}\). Let \(\mathop{\mathrm{origin}}(x_{l+1}) = \{x', x''\}\) and let \(x'\) be the vertex on the shortest path from \(x_l\) to \(x_{l+1}\) in the subdivision graph \(\tilde{G_i}\) guaranteed by Observation [obs:origin-contained-in-every-path], where \(i\) is the distance scale in which \(x_{l+1}\) was inserted. We chose \(y_{k(l+1)} = x'\), thus \(y_{k(l+1)} \in \mathop{\mathrm{origin}}(x_{l+1})\) holds. Since \(y_{k(l)} \in \mathop{\mathrm{origin}}(x_l)\) and \(y_{k(l)} \notin \mathop{\mathrm{origin}}(x_{l+1})\), we have \(|\mathop{\mathrm{origin}}(x_l) \cap \mathop{\mathrm{origin}}(x_{l+1})| \le 1\). It follows that the edge \((y_{k(l)}, x')\) exists in \(E \cup F_R\), since**
If \(\mathop{\mathrm{origin}}(x_l) \cap \mathop{\mathrm{origin}}(x_{l+1}) = \{x'\}\), then \((y_{k(l)}, x') \in E\).
Its weight is given by \(\mathop{\mathrm{w}}_{H_R}((y_{k(l)},y_{k(l+1)})) = \mathop{\mathrm{w}}_{H_R}((y_{k(l)},x')) = \mathop{\mathrm{w}}_G((y_{k(l)},x')) \le \delta(y_{k(l)},x_l) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) - \delta(x',x_{l+1})\).If \(\mathop{\mathrm{origin}}(x_l) \cap \mathop{\mathrm{origin}}(x_{l+1}) = \emptyset\), then we added \(\phi((x_l, x_{l+1})) = \mathop{\mathrm{origin}}(x_l) \times \mathop{\mathrm{origin}}(x_{l+1})\) to \(F_R\). Since \(y_{k(l)} \in \mathop{\mathrm{origin}}(x_l)\) holds by the induction hypothesis, we have \((y_{k(l)}, x_{l+1}) \in F_R\).
The weight of the edge is \(\mathop{\mathrm{w}}_{H_R}((y_{k(l)},y_{k(l+1)})) = \mathop{\mathrm{w}}_{H_R}((y_{k(l)},x')) \le \mathop{\mathrm{w}}_{\phi((x_l,x_{l+1}))}=\delta(y_{k(l)},x_l) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) - \delta(x',x_{l+1})\).
Thus, in both cases the sequence \((y_0,y_1,\dots, y_{k(l)},y_{k(l+1)})\) forms a path in \(H_R\). In addition, for the weight of the edge \((y_{k(l)},y_{k(l+1)}) = (y_{k(l)},x')\) the following holds \[\mathop{\mathrm{w}}_H((x_l,x_{l+1})) \ge \mathop{\mathrm{w}}_{H_R}((y_{k(l)},y_{k(l+1)})) - \delta(y_{k(l)},x_l) + \delta(x',x_{l+1}) \] Hence, we have \[\begin{align} \sum_{i = 0}^{l} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) &= \sum_{i = 0}^{l-1} \mathop{\mathrm{w}}_H((x_i,x_{i+1})) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) \\ &\mathrel{\overset{\text{(IH)}}{\ge}} \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l)}, x_l) + \mathop{\mathrm{w}}_H((x_l,x_{l+1})) \\ &\mathrel{\overset{\text{(c)}}{\ge}} \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l)}, x_l) + w_{H_R}((y_{k(l)},y_{k(l+1)})) - \delta(y_{k(l)},x_l) + \delta(x',x_{l+1}) \\ &= \sum_{i = 0}^{k(l)-1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + w_{H_R}((y_{k(l)},y_{k(l+1)})) + \delta(x',x_{l+1}) \\ &= \sum_{i = 0}^{k(l)} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l+1)}, x_{l+1})\\ &= \sum_{i = 0}^{k(l+1)- 1} \mathop{\mathrm{w}}_{H_R}((y_i,y_{i+1})) + \delta(y_{k(l+1)}, x_{l+1}), \end{align}\] where the final step follows from \(k(l+1)= k(l)+ 1\).
◻
It remains to show that the hopset \(F_R\) inherits the size of the underlying emulator construction.
Lemma 7. Let \(\mathcal{A}\) be an algorithm that, for any \(n\)-vertex graph, constructs an \((\alpha,\beta)\)-emulator of size \(S_{\mathcal{A}}(n,\alpha,\beta)\). Let \(F \subseteq V'\times V'\) be the hopset produced by the construction of Section 2.1 using \(\mathcal{A}\), and let \(F_R\) be the hopset obtained by projection \(F\) onto the vertex set \(V\). Then the size of \(F_R\) is bounded by \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon},\alpha,\beta)\log_{1+\epsilon}(nW))\).
Proof. By Lemma 2 the hopset \(F\) consists of \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon},\alpha,\beta)\log_{1+\epsilon}(nW) + m\frac{t}{\epsilon}\log_{1+\epsilon}(\frac{t}{\epsilon}))\) many edges. As mentioned in the proof of Lemma 2, the second additive term \(O(m\frac{t}{\epsilon}\log_{1+\epsilon}(\frac{t}{\epsilon}))\) arises from the auxiliary edge set \(\tilde{F}\), which contains all edges that connect each vertex \(v \in V_{\text{sub}}\) to the vertices in \(\mathop{\mathrm{origin}}(v)\). Hence, by definition all edges in \((u,v) \in \tilde{F}\) satisfy \(\mathop{\mathrm{origin}}(u) \cap \mathop{\mathrm{origin}}(v) \neq \emptyset\), and are therefore not included in the projected hopset \(F_R\). Furthermore all remaining edges in \(F\setminus \tilde{F}\) are mapped to at most four edges in \(F_R\), and thus the size of \(F_R\) is bounded by \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon},\alpha,\beta)\log_{1+\epsilon}(nW))\) as claimed. ◻
Having established the necessary lemmas, we are now ready to prove Theorem [thm:main].
Proof. Let \(F\) be the hopset produced by the construction in Section 2.1, with \(t = \max(\frac{1}{\epsilon},\frac{\beta}{\epsilon})\), and let \(F_R\) be its projection onto the vertex set \(V\) as described in Section 2.4. By Lemma 7, the number of edges in \(F_R\) is bounded by \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon},\alpha,\beta)\log_{1+\epsilon}(nW)) = O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon},\alpha,\beta)\frac{1}{\epsilon}\ln(nW))\) for \(0 < \epsilon \le 1\). As shown in Lemma 4, \(F\) is a \((\alpha(1+\epsilon), O(\alpha t^2)\ln(nW))\)-hopset of \(G'\) with respect to \(V\). Lemma 6 ensures that \(F_R\) preserves the same stretch and hopbound as \(F\), and Lemma 5 ensures that the distances are not underestimated. Therefore, \(F_R\) is a \((1+\epsilon, O(\alpha t^2)\ln(nW))\)-hopset of \(G\) with size \(O(S_{\mathcal{A}}(n+m\frac{t}{\epsilon},\alpha,\beta)\log_{1+\epsilon}(nW))\) . ◻
References↩︎
Department of Computer Science, University of Salzburg, Austria↩︎
This publication has been supported by the EXDIGIT (Excellence in Digital Sciences and Interdisciplinary Technologies) project, funded by Land Salzburg under grant number 20204-WISS/263/6-6022.↩︎
This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702).↩︎
The edges in \(\tilde{F}\) get removed in the projection back to a hopset on \(G\). See Section 2.4.↩︎