General Multiplicative Spanners in Practice

We present the first practical evaluation of algorithms for decoupled $\alpha$-spanners, comparing solution quality and running times. Our study covers exact approaches, several Greedy variants, LP-rounding approximations, and heuristics derived from ILP formulations. Our hypothesis-driven experiments focus on practical instances from a wide array of applications. Algorithm engineering is used to speed up approaches, allowing us to solve instances with more than $\mathrm{34\hspace{0.17em}000}$ nodes exactly. Greedy often performs well but, in certain cases, yields arbitrarily poor solutions – so practitioners need to be cautious.

Althöfer et al. [4] present the Greedy heuristic for coupled $\alpha$-spanners. It starts with an empty spanner $H=(V,\mathrm{\varnothing })$. Until $H$ is feasible, it processes edges $\{u,v\}\in E$ in non-decreasing order of length. It adds $\{u,v\}$ to $H$ if the current distance between $u$ and $v$ in $H$ is too long. For coupled instances, $\alpha =2k-1$ ($k\in {\mathbb{N}}_{\ge 1}$), Greedy yields spanners of lightness $𝒪(n/k)$ and size $𝒪(n^{1+1/k})$. By violating the stretch-property by a factor of $(1+\epsilon )$, $\epsilon >0$, Greedy yields $(1+\epsilon )(2k-1)$-spanners of lightness $𝒪(n^{1/k}(1+k/({\epsilon }^{1+1/k}\log k)))$ [31]. In the geometric setting, i.e., complete graphs with Euclidean lengths (=weights), it attains lightness $𝒪(\log n)$ and size $𝒪(n)$ [19]. The running time of $𝒪(m(n^{1+1/k}+n\log n))$ is dominated by shortest path computations for each edge. On decoupled instances, these size guarantees still hold, but Greedy offers no weight (nor lightness) guarantee: already the shortest edge (which is always chosen) may have arbitrarily high weight. Nevertheless, Greedy is commonly used in practice also for decoupled instances, see e.g. [64, 5, 45]. For coupled $\alpha$-spanners, many algorithms were developed in an attempt to improve over Greedy [60, 8, 9, 30]; some of them allow the spanners to violate the stretch property by a factor of $1+\epsilon$ [19, 31, 33, 3]. Still, Greedy is beneficial w.r.t. most guarantees and typically outperforms other non-exact approaches in practice [37, 23], often achieving near-optimum weight [16].

The Augmented Greedy [15], extends Greedy to provide weight guarantees in the decoupled setting. For a weight $x$, let $G[x]\subseteq G$ be the weight-restricted subgraph containing only edges of weight at most $x$. First, Augmented Greedy determines a weight threshold $\widehat{w}$, classifying edges as either low- or high-weight. Then, the algorithm runs Greedy on $G$ (in order of edge length), but whenever a high-weight edge $\{u,v\}$ would be added, it adds a shortest path (w.r.t. $\mathrm{\ell }$) from $G[\widehat{w}]$ instead. The threshold $\widehat{w}$ is chosen such that $G[\widehat{w}]$ is a feasible spanner; its value can be found via binary search over the distinct edge weights of the instance; it thus requires $𝒪(\log n)$ feasibility tests. This establishes a weight ratio guarantee of $m$. To additionally retain all quality guarantees of Greedy in coupled settings, $\widehat{w}$ is further raised to the weight $\mathrm{𝑀𝑆𝑇}(G,w)$ of the minimum-weight spanning tree in $G$ (if larger). Augmented Greedy’s running time of $𝒪(m(m+n\log n)\log m)$ closely matches Greedy.

The literature knows two exact ILP formulations for coupled $\alpha$-spanners. It is straight-forward to generalize both to the decoupled case, by naturally adapting the objective function. The first approach employs a path-based ILP for multicommodity flow [61]. For each node pair $\{u,v\}$, let ${𝒫}_{uv}$ be the set of $uv$-paths with length at most $\alpha \cdot {\mathrm{\ell }}_G[u,v,$], and we have binary path variables $y_P$ for each path $P\in {𝒫}_{uv}$. Such a variable is $1$ if and only if $P$ is contained in the solution $H$; it is a witness that its endpoints satisfy the stretch property. Constraints ensure that for every pair $\{u,v\}$, at least one path of ${𝒫}_{uv}$ is chosen. For every $e\in E$ there is a binary edge variable that is $1$ if and only if it is on a chosen path. The $\alpha$-spanner is established by those edge variables. The main challenge lies in the exponential number of path variables that have to be dynamically added to the LP relaxation using column generation. The restricted master problem (RMP) considers only subsets $\mathrm{\varnothing }\ne {𝒫}_{uv}^{\prime }\subseteq {𝒫}_{uv}$ for the path variables. During the solving process, paths are iteratively added, extending the RMP and improving the objective function value. Suitable paths are found by solving the pricing problem, which corresponds to a constrained shortest path (CSP) problem. Paths are constrained in their length w.r.t. $\mathrm{\ell }$ and their cost, which is derived from the edge weights and the current RMP solution. The column generation procedure is repeated until no more paths are found. This establishes an optimal solution to the LP relaxation of the above formulation; an integral optimum solution is then found via Branch-and-Bound.

The other exact ILP approach considers a standard arc-based multicommodity flow model [2]. It has polynomial size and can be solved directly using standard ILP solvers via Branch-and-Bound. For each node pair $\{u,v\}$, it routes one unit of flow from $u$ to $v$, modeled via two directed flow variables per edge. Standard flow conservation constraints establish a flow solution; additional constraints ensure that any integral $uv$-flow follows a simple path of length at most $\alpha \cdot {\mathrm{\ell }}_G[u,v]$.

The original publications consider coupled instances. In [61], the path-based approach fails to solve instances with 64 nodes within 30 minutes. In [2], the arc-based approach requires up to 40 hours for instances with 100 nodes. In [16], algorithm engineering is used to speed up both approaches. They are able to solve coupled instances with more than 16 000 nodes in 13 minutes. Except for instances with unit-lengths or large stretches $\alpha >3$, the path-based approach is superior.

Stronger guarantees for decoupled $\alpha$-spanners require more intricate, randomized algorithms. They all yield feasible solutions with high probability and have expected approximation ratios. Further, they all require polynomially bounded integral lengths and $\alpha$. Some of them are applicable to broader forms of spanner problems.

The first class of approximation algorithms [26, 24, 22, 44] is based on rounding a path-based linear program (LP). Already solving the LP is non-trivial (see above) as guaranteeing polynomial running times requires the use of an FPTAS [55, 48] (and thus integral edge length [65]) to repeatedly solve the CSP pricing problem. Further, as rounding does not settle all node pairs, all of these algorithms require additional elaborate subroutines for, e.g., shallow trees [41] or minimum-weight distance-preserving junction trees [24]. Achieving the formally strongest ratio of $\widetilde{𝒪}(n^{4/5+\epsilon })$ [44] even requires both; $\widetilde{𝒪}$-notation suppresses polylogarithmic factors. To our knowledge, these subroutines remain unimplemented, likely as their expected running times are impractically high. The other algorithms additionally either violate the stretch property [22] or are only applicable to unit-weights or -lengths [26, 24].

Another algorithmic idea is a randomized approximation algorithm for unit-length $\alpha$-spanners, based on rounding an arc-based LP in a layered graph [28]. While a direct extension to non-unit lengths therein is flawed, this was later corrected [15]. This Layered Rounding (LR) algorithm achieves an $𝒪(n\log n)$ approximation ratio for decoupled spanners. Let $L≔{\max }_{e\in E}\mathrm{\ell }(e)$ be the largest edge length, and $\xi ≔\alpha L$ the maximum distance demand. The key idea is to establish a layered graph $G^{\xi }$ consisting of $\xi +1$ layers, each (essentially) a copy of $G$. An arc-based multicommodity flow LP model sends flow through $G^{\xi }$. Given an optimal LP solution, rounding up every edge variable with fractional value ${\chi }_e$ with probability $\pi ({\chi }_e)=\min \{1,\ln (nm{(\xi +2)}^{n-2}){\chi }_e\}$ yields (w.h.p.) a feasible spanner with suitable weight. For instances with constant $\xi$ and maximum node degree, the ratio improves to $𝒪(\log n)$.

Before we consider the implemented algorithms, we discuss our preprocessing techniques. Let $K\subseteq \left(\genfrac{}{}{0pt}{}{V}{2}\right)$ denote the set of node pairs for which the stretch property has to be actively enforced: it is long known that $K=E$ suffices to obtain feasible $\alpha$-spanners [58]. It even suffices to set $K=M$, where $M\subseteq E$ are the metric edges, i.e., those that satisfy the triangle inequality [15]. All algorithms thus start with an all-pairs-shortest-path computation to classify the edges accordingly. In coupled instances, non-metric edges can be removed as they never appear in an optimum solution. In decoupled instances this is no longer true as such edges may be crucial to attain a (near-)optimum solution. We propose two alternative size reduction techniques. Firstly, the notion of metric edges can be generalized: We can remove an edge $e=\{i,j\}\in E$ if it is dominated, i.e., there is an $ij$-path in $G$ that is neither longer nor heavier than $e$. Checking if a given edge is dominated is NP-hard [40] and requires a constrained shortest path algorithm (also used within the path-based ILP, see below); we call this reduction PreD. Secondly, an edge $e=\{i,j\}\in E$ is overlong if $\mathrm{\ell }(e)>\alpha \cdot {\mathrm{\ell }}_G[i,j]$ and can be removed without affecting optimality. Overlong edges can be identified during the detection of metric edges with small overhead. We call this preprocessing strategy PreO.

Despite not providing any non-trivial weight guarantee, Greedy is commonly used in practice to solve decoupled instances, typically by ignoring weights or lengths or by fusing both. We consider two variations of Greedy, which only differ in the order in which edges are considered; both guarantee a feasible solution. G-LW orders edges lexicographically by their length and weight. It has no weight guarantees, but a size guarantee of $𝒪(n^{1+1/k})$ in general, and $𝒪(n)$ in the geometric setting. Conversely, G-WL orders edges lexicographically by their weight and length, which yields no quality guarantees at all. Intuitively, while G-LW tries to select as few edges as possible, G-WL tries to avoid selecting expensive edges. Clearly, in coupled, unit-weight or unit-length scenarios, both algorithmic variants behave identically.

We consider two variations of Augmented Greedy that only differ in the weight threshold. AG uses the weight bound as proposed in [15]. AGT does not use $\mathrm{𝑀𝑆𝑇}(G,w)$ to further raise the weight threshold after the binary search. It has the same weight guarantee as AG for decoupled instances, but not for coupled ones. Observe that whenever $\mathrm{𝑀𝑆𝑇}(G,w)$ is larger than the maximum edge weight, AG and G-LW yield the same spanner. We may assume that this is a common trait in real-world instances. In these cases AGT will typically classify fewer edges as low-weight (and consequently may yield solutions with smaller maximum edge weights). We can further speed up AG by changing the computation order proposed in [15]: We start with first computing $\mu ≔\mathrm{𝑀𝑆𝑇}(G,w)$. If $G[\mu ]$ is a feasible spanner, we have $\widehat{w}=\mu$; otherwise, we perform the binary search only for edge weights larger than $\mu$.

Both above ILP approaches can be used to tackle decoupled instances, but unfortunately, not all of the speedup techniques of [16] are analogously applicable. Some of them can be salvaged, however. We denote the path-based and arc-based approaches by PB and AB, respectively. For both, we provide an initial heuristic solution obtained by G-LW. We use $K=M$ instead of $K=E$: while we do not have to consider non-metric edges in $K$, we cannot delete them (as was possible in the coupled case).

For PB, for all $\{u,v\}\in K$, we do the following: If there is a unique feasible $uv$-path, we fix this path’s variable and associated edge variables. We prune CSP calls if we can deduce that they are futile based on previous pricing iterations where no path was found. Initially, we add up to $10$ shortest $uv$-paths to the formulation; during pricing, we add up to $3$ lowest cost non-dominated feasible CSP solutions. In contrast to [16], we stop and return the first one if it has cost $0$, as no further non-dominated paths can exist. Modern ILP-solvers strongly benefit from automatic cut generation (e.g., Gomory cuts [7]). Typically, such cuts can only be generated from constraints that will no longer change during the computation. As column generation regularly updates constraints with new variables, [16] does not use automatic cut generation. We can do better: for $\{u,v\}$, if all feasible $uv$-paths are present after initialization, we safely enable cut generation based on its corresponding constraints. These node pairs are subsequently ignored during pricing. Our pilot studies suggest that this vastly improves performance, especially on instances with unit weights or lengths.

For AB, if an edge direction $ij$, $\{i,j\}\in E$, is unreachable for some commodity $\{u,v\}\in K$, i.e., ${\mathrm{\ell }}_G[u,i]+\mathrm{\ell }(\{i,j\})+{\mathrm{\ell }}_G[j,v]>\alpha \cdot {\mathrm{\ell }}_G[u,v]$, we fix the corresponding flow variable to $0$. If, in contrast, $ij$ is used in every feasible $uv$-path, the corresponding flow variable is mandatory and fixed to $1$. Since $K=M$, the latter case may apply only (if at all) for elements of $K$. Furthermore, AB may profit from all automatic cut generations and generic primal heuristics (like the feasibility pump) used by the ILP-solver (see below).

As argued above, most strong LP-rounding based approximation algorithms are unfortunately futile to implement. However, the Layered Rounding approach, denoted LR, seems plausible to implement. Similar to AB, we can fix unreachable and mandatory variables and set $K=M$. LR chooses each edge with some probability $\pi ({\chi }_e)$, which increases for larger LP-values ${\chi }_e$ corresponding to edge $e$. If the solution is infeasible, the rounding is redone. W.h.p., the first attempt already yields a feasible solution (of weight corresponding to the expected approximation guarantee).

However, it stands to argue that probability $\pi ({\chi }_e)$ may be rather high (to achieve the guarantees), and some smaller probabilities (yielding lower-weight solutions) may suffice for feasibility in practice. We thus also consider an algorithmic variant LR-R which uses a repeated rounding scheme (not to confuse with iterative rounding): For increasing values $k=0,1,\mathrm{\dots }$, we consider the probability function ${\pi }_k({\chi }_e)≔\min \{1,b^k\cdot {\chi }_e\}$, for some $b\in {\mathbb{Q}}_{>1}$, to sample (based on the single computed LP-solution) subgraphs $H_k$. We stop once the first such subgraph is feasible. Note that after $𝒪(\log n)$ steps $b^k{\chi }_e\ge \pi ({\chi }_e)$, LR-R finds a feasible solution w.h.p., and we do not increase $k$ for any further attempts.

There are also further feasible practical heuristic ideas that can be considered to put LR’s performance in context. For both, we start with computing the LP-relaxation of the AB ILP model (including fixing unreachable and mandatory variables). AB-R then uses the repeated rounding scheme describes above, increasing $k$ until it finds a feasible solution. AB-F uses the feasibility pump algorithm [38, 11], which is commonly implemented in strong ILP-solvers to identify feasible integral solutions from any LP-solution. Feasibility pump is known to yield strong results for other problems [10], and can be seen as an off-the-shelf method any practitioner may try without much implementation effort, to quickly attain a primal heuristic. We do not consider heuristics based on the PB model, as even completing the formulation with all necessary path variables is to laborious to be considered a practical heuristic.

For both LR-R and AB-R, pilot studies for different choices for $b\in (1,3]$ suggest that the differences in running times and solution quality are negligible. We hence use $b=1.1$.

We design our experiments around concrete hypotheses, as listed in Table 2. We give the intuitive corresponding rationals when discussing them in detail in Section 5. The table also summarizes the results of testing them, see Section 5. Overall, (H2) to (H5) investigate how problematic the widespread practice of using G-LW or G-WL on decoupled instances truly is and whether adapted variants yield better results. (H6) assesses what instances can be solved exactly, while (H7) to (H9) explore the practicality of non-exact LP-based approaches. Lastly, (H10) and (H11) formulate high-level take-away messages.

We focus our evaluations on practically motivated instances from a variety of backgrounds. In practice, stretch factors $\alpha$ are typically small constants. Often stretches $\alpha >3$ are considered impractical, e.g., [64, 45], as they yield too large distortions. Thus, we mainly consider $\alpha \in \{1.3,\mathrm{\hspace{0.17em}2},\mathrm{\hspace{0.17em}3}\}$, also in line with previous studies. To check trends for degenerating stretches, we also consider $\alpha =5$. Let $W_{\text{1}}$ ($L_{\text{1}}$) denote unit weights (lengths); other indices denote other measures. We do not consider $L_{\text{1}}$ instances for $\alpha =1.3$, as they are trivial. Let $\overline{\delta }$ denote the average node degree, and $\rho$ ($\overline{\rho }$) the (average) Pearson correlation coefficient between weights and lengths:

Power. Graphs from power transmission line routing [14] based on an area of $6\times 3$ km² near Münster, Germany. The resulting graph ($n=1859,m=6337$) is a Moore neighborhood grid graph with holes. Besides $W_{\text{1}}$, we consider weights corresponding to the intersection with bird preservation areas, landscape preservation areas, freeways, or settlement areas. Lengths correspond to Euclidean distances ($\overline{\rho }\in [0.08,0.15]$).

Road. Motivated by [45], we consider 10 undirected US road networks [13] with and $\overline{\delta }\in [2.3,2.9]$. We consider combinations $(W_{\text{1/}\text{lim}},L_{\text{len}})$, $(W_{\text{1}},L_{\text{len}})$ and $(W_{\text{gas}},L_{\text{t}})$ with $\overline{\rho }\approx -0.06,0,0.94$, respectively. Thereby $W_{\text{1/}\text{lim}}$ is the inverse speedlimit, $W_{\text{gas}}$ the fuel consumption [56], $L_{\text{t}}$ the travel-time, and $L_{\text{len}}$ the road segment’s length.

Repetita. An internet traffic engineering benchmark set [42], where the given (integer) delay are the edge lengths. We include the three largest Internet Topology Zoo [51] instances ($W_{\text{1}}$) with $n\in [149,197]$, $\overline{\delta }\in [2.3,2.6]$, and $\overline{\rho }\approx 0$. We also use all six Rocketfuel [62] instances which have given edge weights, $n\in [79,315]$, $\overline{\delta }\in [2.9,6.2]$, and $\overline{\rho }=0.20$.

STL. Motivated by applications in VLSI design [6], we consider the rectilinear and VLSI instance sets from SteinLib [52]. We have $n\in [12,\mathrm{38\hspace{0.17em}418}]$ (median $391$), $\overline{\delta }\in [1.8,3.8]$, and a Manhatten metric between nodes. We consider $(W_{\text{1}},L_{\text{man}})$ and $(W_{\text{man}},L_{\text{man}\text{<sup class="ltx\_sup"><span class="ltx\_text" style="font-size:70\%;">2</span></sup>}})$ ($\overline{\rho }\approx 0$ and $0.79$); totaling $306$ VLSI and $576$ rectilinear graphs. $L_{\text{man}\text{<sup class="ltx\_sup"><span class="ltx\_text" style="font-size:70\%;">2</span></sup>}}$ corresponds to the Elmore delay [35], i.e., delays over wires are (rougly) squares of their length.

SBM. In [5], spanners are used to minimize ink usage in graph drawings. We consider their 100 social network graphs [54] generated using the stochastic block model [46] with $n\in [20,200]$. Average node degrees vary from sparse ($\overline{\delta }\in [4,8]$) to dense ($\overline{\delta }\ge 20$). Euclidean edge lengths are attained via stress majorization [39, 66]; weights are the inverse neighboring edge betweenness (and ${10}^8$, if betweenness is $0$), see [5] ($\overline{\rho }=0.04$).

EPB. For sparsification in graph drawings via edge-path bundling, [64] uses spanners. We use their Airlines ($n=235$, $m=1297$), Migration ($n=1702$, $m=6487$), and Airtraffic ($n=1533$, $m=16480$) instances with $W_{\text{1}}$ and squared Euclidean distances ($\overline{\rho }\approx 0$).

We use decoupled generalizations of previously considered synthetic instances [61, 37, 2, 23, 16].

ER. Erdős-Rényi graphs are expanders w.h.p. [47], i.e., simultaneously sparse and highly connected. We enforce relative densities $r\in R≔\{10\%,50\%\}$ (dense) or constant $\overline{\delta }\in D≔\{4,8\}$ (sparse). For each $n\in N≔\{20,50,100,200,500,1000,2000,5000\}$ and $r\in R$ ($\overline{\delta }\in D$), each possible edge is included with uniform probability $r$ ($\overline{\delta }/(n-1)$, resp.).

GEO. Geometric graphs are complete graphs ($r=100\%$) with Euclidean lengths (see below). We consider all $n\in N\setminus \{2000,5000\}$.

For ER, we consider combinations $(W_{\text{1}},L_{\text{n}})$, $(W_{\text{n}},L_{\text{1}})$, and $(W_{\rho },L_{\text{n}})$; for GEO, $(W_{\rho },L_{\text{euc}})$ and $(W_{\text{1}},L_{\text{euc}})$. For $L_{\text{n}}$, values are drawn uniformly at random from $\{1,2,\mathrm{\dots }n\}$ [22, 16]; Euclidean lengths $L_{\text{euc}}$ arise from placing nodes uniformly at random in a unit square. We obtain weights $W_{\rho }$ synthetically based on given $\rho \in \{-1,-0.7,0,0.7\}$, using the linear combination method: Set $w^{\prime }(e)≔\mathrm{\ell }(e)$ and randomly shuffle them between the edges. Then, set $w(e)≔w^{\prime }(e)+(\sqrt{1-{\rho }^2}/\rho )\mathrm{\ell }(e)$ to achieve the target correlation $\rho$. For each of these parameter tuples, we generate 5 ER (GEO) graphs, yielding $960$ ($150$, resp.) graphs overall.

OrbWeb. When considering spanners for passenger assignment [45], highly structured orb-webs [34] were proposed. Even their largest considered instance ($n=101$, $m=200$, $(W_{\text{1}},L_{\text{euc}})$, $\overline{\rho }\approx 0$) is trivial to solve exactly for all considered $\alpha$; we thus refrain from considering them in detail in the following.

We say an exact (non-exact) algorithm fails if it does not return a proven optimal (any, respectively) solution within the time and RAM limit. When discussing the running time ratio or weight ratio between two algorithms $X$ and $Y$ (writing $X$/$Y$), we define this ratio be $1$ ($0$) if both (only $Y$, respectively) fail(s). We rarely consider cases where only $X$ may fail; then we use the time limit or weight of $G$ for $X$.

Our evaluation follows a two-phased approach. First, we analyze the median and other quantiles of paired performance metrics (running time, weight ratio, etc.) to obtain an initial assessment of algorithmic differences. If these descriptive statistics are inconclusive, we proceed with the Wilcoxon signed-rank test to formally assess statistical significance. All hypothesis tests are conducted at a $p$-value threshold of $0.05$. This methodology leverages robust non-parametric statistics and avoids unnecessary testing when strong distributional shifts are evident from summary statistics.

PreD is computationally costly. If we could reject (H1.D) at all, it would be for long-running algorithms on instances with many dominated edges. Instances with unit-weights or metric lengths (and our ER ) have no dominated edges. Consider PB (results are similar for the other (I)LP-based algorithms). Even on the remaining instances, PreD never yields lower failure rates than PreO: on ER $(W_{\rho \ge 0},L_{\text{n}})$, the gaps are $5$–$7$ percentage points for all values of $\alpha$. Interestingly, for $\alpha =2$ and $5$, even using neither PreD nor PreO performs slightly better than PreD (see Table 5). We thus accept (H1.D) .

Overlong edges only exist in instances with non-metric lengths. The number of overlong edges decreases with growing $\alpha$ and increases with relative density. Naturally, greedy algorithms get little to no benefit from PreO. PB with PreO never has a higher failure rate than without preprocessing. On ER $(W_{\rho },L_{\text{n}})$, using PreO reduces failure rates by $3$–$7$ percentage points for different values of $\alpha$. On the naturally sparse STL $(W_{\text{man}},L_{\text{man}\text{<sup class="ltx\_sup"><span class="ltx\_text" style="font-size:70\%;">2</span></sup>}})$, their failure rates never deviate more than $1$ percent points. Even on instances without overlong edges, PreO increases the runtime by a mean of only $0.3\%$. We accept (H1.O) and always use PreO for all (I)LP-based approaches and never use PreD for any algorithm below.

The rationale to (H2) is G-WL’s complete lack of quality guarantees. We expect that the overall weight, size, and running time of G-LW is not higher and often lower than that of G-WL. By definition, both algorithms yield the same solution on unit-length or unit-weight instances; we shall not consider them now. G-LW generally finds lower weight solutions, cf. Figure 1. The difference is especially large on strongly anti-correlated instances, where G-WL tends to select almost the entire graph, as it considers edges in (nearly) descending order of length. On all considered instance sets, Wilcoxen signed-rank tests confirm that G-LW yields solutions also of lower size (not only weight).

Their running times are very similar on real-world instances (cf., Tab. 3 or Fig. 2). The $0.75$, $0.5$, and $0.25$ quantiles of the running time ratios G-LW/G-WL are $1.25$, $1.00$, and $0.87$, respectively. G-WL often benefits from the fact that the shortest path computation in the current spanner can terminate early as all its current edges are too long (at the cost of a large spanner). On dense graphs (e.g. GEO $(W_{\rho },L_{\text{euc}})$), this backfires as the spanners become unwieldily large, as witnessed by the median sparsity $0.2\%$ by G-LW vs. $6.4\%$ by G-WL. For $\rho \in \{-1,-0.7\}$, G-WL is significantly slower and even fails more often. Thus, we accept (H2) .

(H3) assumes that, in practice, edges rarely have a weight larger than $\mathrm{𝑀𝑆𝑇}(G,w)$. This is true for all instances, except for SBM. In the former cases, AG then classifies all edges as low weight, and AG and G-LW yield the same solution by construction. In SBM, some edges weight more than $\mathrm{𝑀𝑆𝑇}(G,w)$. The vast majority are edges that have betweenness $0$ and hence weight ${10}^8$. These edges are metric and thus neither dominated nor overlong and cannot simply be removed from the instance (see Section 3). There are 13 instances, where G-LW’s weight ratio to the optimum is larger than $6\cdot {10}^5$. In contrast, the maximum weight ratio of AG to the optimum is $6$, achieving order of magnitude lower weight. Crucially, across all considered instances, AG never returns a worse solution than G-LW. We reject (H3.W) in its generality but accept it for all instance sets except SBM for the expected reason.

AG and G-LW have identical failure rates for every considered instance and are the most successful among all considered approaches. Recall that for all instances (except SBM) AG’s computation is essentially a single $\mathrm{𝑀𝑆𝑇}(G,w)$ computation (to a large $\widehat{w}$), followed by G-LW. In $90\%$, $75\%$ and $50\%$ of the non-SBM instances where G-LW requires at least 1 s, the running time ratio AG/ G-LW is below $1.48$, $1.36$, and $1.24$, respectively. On all SBM instances, the median ratio is $1.03$. Hence, we accept (H3.T) as well.

(H4) ’s rationale is that classifying more edges as high-weight is beneficial but obtaining the suitable bound takes extra time. AGT nearly never fails, except on some large ER $(W_{\text{n}},L_{\text{1}})$ and GEO $(W_{\rho },L_{\text{euc}})$ instances. This is due to the many binary search steps for $\widehat{w}$, each requiring a feasibility check (and associated shortest path computations) that is expensive on large, dense graphs. For all instances solved by both AG and AGT and where AG’s running time is at least 1 s, the $0.95$, $0.75$, $0.5$, and $0.25$ quantile of the running time ratio AGT/AG is $1.36$, $1.10$, $1.01$, and $0.98$, respectively. We accept (H4.T) .

Since, AG and G-LW behave identical on all non-SBM instances, we consider SBM now, and defer for the other instances to the analysis of (H5) . We have an intrinsic dependency on $\alpha$: For $\alpha =1.3$, $2$, $3$, and $5$, AG and AGT yield different weight solutions in $2$, $16$, $41$, and $74$% of the instances; when they differ, AGT finds a lower weight solution in $100$, $87.5$, $95.1$, and $90.5$% of the instances, respectively. On SBM instances, we accept (H4.W) . As we will see in (H5) , the situation is not as clear cut on other instance sets.

(H5) compares AGT and G-LW and, by extension, AG. Consider (H5.W) and (H5.C) first. Since, by design, they yield identical solutions for unit-weight ($W_1$) instances, we ignore those here. On real-world instances, the $0.95$ to $0.05$ quantiles of the weight ratio AGT/G-LW are all $1$. For Road, Power, and Repetita Rocketfuel instances, the maximum difference in weight is $5\%$. The maximum weight ratio over all non-$W_{\text{1}}$ instances (including the synthetic ones) is below $1.19$; the $0.9$ to $0.4$ quantiles are all $1$; even the $0.2$ and $0.1$ quantiles are still $0.98$ and $0.92$; the minumum ratio (close to $0$) arises for the SBM instances as discusses before. Hence, for the vast majority of instances they yield essentially the same weight, see also Figure 2. However, (H5.W) is verified by Wilcoxon signed-rank test for ER $(W_{\text{n}},L_{\text{1}})$ and $(W_{\rho \ge 0},L_{\text{n}})$, GEO $(W_{\rho \ge -0.7},L_{\text{euc}})$, and SBM. For all other non-$W_{\text{1}}$ instance sets it is inconclusive. Notably, contrary to our expectations, also on (strongly) anti-correlated instances – rejecting (H5.C) . We cannot accept (H5.W) (and thus neither (H4.W) ) in generality, but the data is also not sufficient for definite rejection.

Similarly, the maximum size ratio of AGT/G-LW over all instances is $1.21$, the $0.9$ quantile is $1.02$ (cf. Figure 2 for the same reason as above). All quantiles between $0.8$ and $0.1$ are $1.00$. The minimum size ratio is $0.95$. Hence, for the vast majority of instances they yield similarly sized solutions. Whenever AGT achieves lower size, it also achieves lower weight. Further, in Figure 2, we see that G-LW typically yields lower size solutions than AGT, even when it yields higher weight. Thus, we see no reason to reject (H5.S1) .

(H5.S2) ’s rationale is that G-LW has a tight size guarantee assuming Erdős’ girth conjecture [36]. On all unit-weight instances – the respective Power, Road, STL, EPB, ER and GEO instances – the $0.5$- and $0.75$-quantile of the observed weight ratio of G-LW to the optimum is always below $1.02$ and $1.06$, respectively, for all $\alpha \le 3$ (except for GEO where lower bounds are weak). We thus accept (H5.S2) .

Consider (H5.T) . For instances solved by both G-LW and AGT, where G-LW’s running time is at least 1 s, the $0.95$, $0.75$, $0.5$, and $0.25$ quantile of the running time ratio AGT/G-LW is $1.76$, $1.41$, $1.30$, and $1.20$, respectively. Overall, we accept (H5.T) .

(H6.T1) is motivated by the observation that the path-based approach outperforms the arc-based one for the coupled case (except for unit weights and lengths, where arc-based dominates) [16]. Table 3 often shows similar failure rates for PB and AB. This even holds for instances with unit weights or lengths (possibly due to the newly introduced automatic cut generation for PB). Only on Road instances with $\alpha \ge 3$, PB fails slightly more often. In contrast, on SBM, EPB, and ER, PB achieves substantially lower failure rates, with particularly drastic differences on SBM. Overall, AB only seems to be slightly better suited for naturally sparse graphs. Otherwise PB is superior. These trends become even more apparent when investigating the running times (see also the performance diagram Figure 2 for $\alpha =2$; for other values the key observations are consistent). Clearly, PB is able to solve more instances more quickly. We accept (H6.T1) .

(H6.T2) seems plausible as the CSP algorithm in PB benefits from correlated weights and lengths. We may consider ER $(W_{\rho },L_{\text{n}})$ and GEO $(W_{\rho },L_{\text{euc}})$, for varying correlations $\rho$. Surprisingly, neither approach seems to be particularly strongly affected by different correlations. Both are marginally more successful for uncorrelated weights and lengths. For ER $(W_{\rho },L_{\text{n}})$ failure rates of PB (AB) for $\alpha =1.3$, $2$, $3$, $5$ do not vary by more than $0$, $1$, $0$, $15$ ($0$, $3$, $4$, $7$, respectively) percent points between different values of $\rho$, and similarly for GEO $(W_{\rho },L_{\text{euc}})$. The dependence seems only relevant for the practically less relevant $\alpha =5$. Overall, we thus have to reject (H6.T2) .

The rationale behind (H7.T) is that the arc-based ILP often achieves integral solutions on coupled instances within the root node [16]. Generally, the failure rates of AB-F and AB-R are at most as high as those of AB (cf. Table 3) and their running times are lower. However, there are notable exceptions. For very dense graphs, AB-F struggles, e.g., for GEO $(W_{\text{1}},L_{\text{euc}})$ or $(W_{\rho },L_{\text{euc}})$ instances with $\alpha =1.3$, its failure rate is $3$–$10$ percentage points higher than that of AB. Conversely, for sparse graphs AB-R underperforms: On the STL and Road instance sets (unless $\alpha =5$), its failure rate is never better than AB’s. There, AB-R requires numerous rounding attempts to obtain a feasible solution. For example, for $\alpha =3$, AB-R is only able to solve a single Road $(W_{\text{gas}},L_{\text{t}})$ instance, and on it requires $38$ rounding attempts (and, thus, feasibility checks). Consider the running time ratios on real-world instances for $\alpha \le 3$. The $0.75$, $0.5$, and $0.25$ quantiles for AB/AB-R, are $1.2$, $1.0$, and $0.7$, respectively; for AB/AB-F, they are $1.4$, $1.2$, and $1.1$, respectively. For these instances, AB-F is slightly faster than AB-R. For $\alpha =2$ this can also be seen in the performance diagram Figure 2: AB-F performs comparable to AB, while both outperform AB-R. Only for $\alpha =5$, due to the low success rate of AB, AB-F and AB-R achieve substantial speed-ups. However, for most (and the practically most relevant) $\alpha$-values, we accept (H7.T) .

Generally, AB-F yields lower weight solutions than AB-R (see Figure 1). The difference is especially large for Road, STL, and SBM instances or for larger $\alpha =3$. For $\alpha =1.3$ (sometimes even $\alpha =2$), both typically yield optimum solutions. Overall, we see no reason to reject (H7.W) , and thus accept it.

By design, LR and LR-R are only applicable to instances with integer lengths and integer $\alpha$. Due to the high number of necessary layers, LR and LR-R’s failure rates (see Table 3) are always higher than those of the exact algorithms, except for ER with $(W_{\text{n}},L_{\text{1}})$ (where only $\alpha$ layers are generated). Still, even for these instances, they never yield better solutions than the significantly faster G-LW. As LR and LR-R offer no recognizable benefit in any scenario, discussing their corresponding hypotheses in detail seems dispensable given the space restriction; see Table 2 for the results.

For (H10) , we compare the strong LP-based approaches (AB-R, AB-F) to the strong greedy approaches (G-LW, AG, AGT). The idea behind (H10) is that Greedy is known to yield strong results in the coupled setting [16, 23, 37] and these qualities may translate to the decoupled setting. On many instance sets, the failure rate of the strong greedy approaches is substantially lower than those of the LP-based approaches (see Table 3); indeed, whenever any strong greedy approach failed an instance, all LP-based approaches failed as well. As a clear example, G-LW and AG never fail on GEO instances, including $n=1000$, while LP-based approach fail on all such instances with $n>50$. For each instance, consider the running time ratio of the slowest strong greedy approach to the fastest LP-based approach. There are only $69$ out of $\mathrm{8\hspace{0.17em}404}$ instances where this ratio is greater than 1. On real-world instances, the $0.98$, $0.75$, $0.5$ and $0.25$ quantiles are $0.93$, $0.43$, $0.21$ and $0.05$, respectively. Similarly, for the synthetic instances, they are $0.82$, $0.13$, $0.01$, and $0.00$, respectively. Clearly, the strong greedy approaches are generally substantially faster and able to tackle larger instances, confirming (H10.T) .

Consider the weight ratio between the highest weight solution obtained by any strong greedy approach and the lowest weight solution obtained by any LP-based approach. On real-world instances, the $0.98$, $0.75$, $0.5$ and $0.25$ quantiles are $1.50$, $1.02$, $1.00$, $1.00$, respectively. For the synthetic instances, they are $2.11$, $1.24$, $1.01$, and $0.00$, respectively. Thus, the greedy approaches yield solutions of similar, but also slightly heavier, weight. Hence, we reject (H10.W) in its generality. Yet, for Power, Repetita, and EPB (H10.W) is confirmed using the Wilcoxon signed-rank test.

Regarding (H11.E) , (H6.T) already establishes that the vast majority of the considered real-world instances can be solved exactly by PB or AB (see also Figure 2). This includes, e.g., STL instances with more than $\mathrm{34\hspace{0.17em}000}$ nodes. Hence, we accept (H11.E) .

For (H11.L) , to be considered worthwhile, a non-exact algorithm must be faster than exact approaches. (H7.T) already confirms that AB-F and AB-R do not offer a significant speed-up against AB, and (H6.T) establishes that PB is faster and able to solve more and larger instances than AB. See also Figure 2 for $\alpha =2$. For $\alpha =3$, only on Power instances, AB-F and AB-R are clearly stronger than AB or PB; but there, the strong greedy algorithms yield better solutions even faster (see also Table 3 and Figure 1). We thus accept (H11.L) .

For (H11.G) , we consider solutions within $5\%$ of the optimum to be “near-optimum”. Consider the ratio of the best solution found by a greedy approach to the optimum (or best found lower bound). We do not make claims for $\alpha =5$, as we do not have enough proven optimal solutions for statistical significance. Over all real-world instances, for each $\alpha \le 3$, the $0.75$, $0.5$, and $0.2$5 quantiles are at most $1.06$, $1.02$, and $1.01$, respectively. Even for nearly every individual instance set and $\alpha \le 3$, the median (and often even the 0.75 quantile) are below the required $1.05$ – exceptions for $\alpha \ge 3$ are SBM, ER $(W_{\text{n}},L_{\text{1}})$, Power, and for $\alpha \ge 2$ Repetita Rocketfuel, GEO $(W_{\rho },L_{\text{euc}})$ (see Figure 1). We only have weak lower bounds for Power and GEO.

For coupled instances, Greedy [4] was reported to yield improved approximation ratios as the instances become larger [16, 61]. For G-LW, AG, and AGT, regardless of $\alpha$, we observe the same trend in the decoupled scenario on SBM and ER $(W_{\text{1}},L_{\text{n}})$, $(W_{\text{n}},L_{\text{1}})$, and $(W_{\rho },L_{\text{n}})$ instances. However, we do not see it for Road and STL instances. Overall, we cautiously accept (H11.G) in general, but without the claim for improved quality on larger instances.

In a nutshell, our study finds that many real-world decoupled $\alpha$-spanner problem instances ($95.8\%$ over the practically relevant $\alpha \le 3$, and still $86.7\%$ including $\alpha =5$) can be solved exactly – typically with the path-based ILP (PB). This includes VLSI derived STL (i.e., SteinLib) instances with more than 34 000 nodes. LP-based approximations (or heuristics) are never (or typically not, respectively) worthwhile. The traditional Greedy (with lengths as primary sorting criterion, G-LW) often works quite well, but there are practical instances (SBM, arising in graph drawing) where it systematically attains solutions of abysmal quality. Thus, practitioners should use it with caution or opt for the augmented AG variant, which offers a good compromise between solution quality and speed.