Multi-level Weighted Additive Spanners¹¹1This paper has been accepted in the 19th Symposium on Experimental Algorithms, SEA 2021.

This paper studies spanners of undirected input graphs with edge weights. Given an input graph, a spanner is a sparse subgraph with approximately the same distance metric as the original graph. Spanners are used as a primitive for many algorithmic tasks involving the analysis of distances or shortest paths in enormous input graphs; it is often advantageous to first replace the graph with a spanner, which can be analyzed much more quickly and stored in much smaller space, at the price of a small amount of error. See the recent survey [5] for more details on these applications.

Spanners were first studied in the setting of multiplicative error, where for an input graph $G$ and an error (“stretch”) parameter $k$, the spanner $H$ must satisfy $\operatorname{dist}_{H}(s,t)\leq k\cdot\operatorname{dist}_{G}(s,t)$ for all vertices $s,t$. This setting was quickly resolved in a seminal paper by Althöfer, Das, Dobkin, Joseph, and Soares [8], where the authors proved that for all positive integers $k$, all $n$-vertex graphs have spanners on $O(n^{1+1/k})$ edges with stretch $2k-1$, and that this tradeoff is best possible. Thus, as expected, one can trade off error for spanner sparsity, increasing the stretch $k$ to pay more and more error for sparser and sparser spanners.

For very large graphs, purely additive error is arguably a much more appealing paradigm. For a constant $c>0$, a $+c$ spanner of an $n$-vertex graph $G$ is a subgraph $H$ such that $\operatorname{dist}_{H}(s,t)\leq\operatorname{dist}_{G}(s,t)+c$ for all vertices $s,t$. Thus, for additive error the excess distance in $H$ is independent of the graph size and of $\operatorname{dist}_{G}(s,t)$, which can be large when $n$ is large. Additive spanners were introduced by Liestman and Shermer [28], and followed by three landmark theoretical results on the sparsity of additive spanners in unweighted graphs: Aingworth, Chekuri, Indyk, and Motwani [7] showed that all graphs have $+2$ spanners on $O(n^{3/2})$ edges, Chechik [17, 13] showed that all graphs have $+4$ spanners on $O(n^{7/5})$ edges, and Baswana, Kavitha, Mehlhorn, and Pettie [11] showed that all graphs have $+6$ spanners on $O(n^{4/3})$ edges.

Despite the inherent appeal of additive error, spanners with multiplicative error remain much more commonly used in practice. There are two reasons for this.

1. 1.

   First, while the multiplicative spanner of Althöfer et al [8] works without issue for weighted graphs, the previous additive spanner constructions hold only for unweighted graphs, whereas the metrics that arise in applications often require edge weights. Addressing this, recent work of the authors [3] and in two papers of Elkin, Gitlitz, and Neiman [22, 23] gave natural extensions of the classic additive spanner constructions to weighted graphs. For example, the $+2$ spanner bound becomes the following statement: for all $n$-vertex weighted graphs $G$, there is a subgraph $H$ satisfying $\operatorname{dist}_{H}(s,t)\leq\operatorname{dist}_{G}(s,t)+2W(s,t)$, where $W(s,t)$ denotes the maximum edge weight along an arbitrary $s\leadsto t$ shortest path in $G$. The $+4$ spanner generalizes similarly, and the $+6$ spanner does as well with the small exception that the error increases to $+(6+\varepsilon)W(s,t)$, for $\varepsilon>0$ arbitrarily small which trades off with the implicit constant in the spanner size.

2. 2.

   Second, $\text{poly}(n)$ factors in spanner size can be quite serious in large graphs, and so applications often require spanners of near-linear size, say $O(n^{1.01})$ edges for an $n$-vertex input graph. The worst-case spanner sizes of $O(n^{4/3})$ or greater for additive spanner constructions are thus undesirable, and unfortunately, there is a theoretical barrier to improving them: Abboud and Bodwin [1] proved that one cannot generally trade off more additive error for sparser spanners, as one can in the multiplicative setting. Specifically, for any constant $c>0$, there is no general construction of $+c$ spanners for $n$-node input graphs on $O(n^{4/3-0.001})$ edges. However, the lower bound construction is rather pathological, and it is not likely to arise in practice. It is known that for many practical graph classes, e.g., those with good expansion, near-linear additive spanners always exist [11]. Thus, towards applications of additive error, it is currently an important open question whether modern additive spanner constructions on practical graphs of interest tend to exhibit performance closer to the worst-case bounds from [1], or bounds closer to the best ones available for the given input graphs. (We remark here that there are strong computational barriers to designing algorithms that achieve the sparsest possible $+c$ spanners directly, or which even closely approximate this quantity in general [18]).

The goal of this work is to address the second point, by measuring the experimental performance of the state-of-the-art constructions for weighted additive spanners on graphs generated from various popular random models and measuring their performance. We consider both $+cW$ spanners (where $W=\max_{uv\in E}w(uv)$ is the maximum edge weight) and $+cW(\cdot,\cdot)$ spanners, whose additive error is $+cW(s,t)$ for each pair $s,t\in V$. We are interested both in runtime and in the ratio of output spanner size to the size of the sparsest possible spanner (which we obtain using an ILP, discussed in Section 5). We specifically consider generalizations of the three staple constructions for weighted additive spanners mentioned above, in which the spanner distance constraint only needs to be satisfied for given pairs of vertices.

In particular, the following extensions are considered. A pairwise spanner is a subgraph that must satisfy the spanner error inequality for a given set of vertex pairs $P$ taken on input, and a subsetwise spanner is a pairwise spanner with the additional structure $P=S\times S$ for some vertex subset $S$. See [31, 21, 27, 26, 12, 20, 14, 15] for recent prior work on pairwise and subsetwise spanners. We also discuss a multi-level version of the subsetwise additive spanner problem where we have an edge-weighted graph $G=(V,E)$, a nested sequence of terminals $S_{\ell}\subseteq S_{\ell-1}\subseteq\cdots\subseteq S_{1}\subseteq V$ and a real number $c\geq 0$ as input. We want to compute a nested sequence of subgraphs $G_{\ell}\subseteq G_{\ell-1}\subseteq\cdots\subseteq G_{1}$ such that $G_{i}$ is a $+cW$ subsetwise spanner of $G$ over $S_{i}$. The objective is to minimize the total number of edges in all subgraphs. Similar generalizations have been studied for the Steiner tree problem under various names including Multi-level Network Design [9], Quality of Service Multicast Tree (QoSMT) [16, 25], Priority Steiner Tree [19], Multi-Tier Tree [29], and Multi-level Steiner Tree [2, 6]. However, multi-level or QoS generalizations of spanner problems appear to have been much less studied in literature. Section 2 generalizes the $+2$ subsetwise construction [21], and Section 4 generalizes to the multi-level setting.

All unweighted graphs have polynomially constructible $+2$ subsetwise spanners over $S\subseteq V$ on $O(n\sqrt{|S|})$ edges [31, 21]. For weighted graphs, Ahmed et al. [3] recently give a $+4W$ subsetwise spanner construction, also using $O(n\sqrt{|S|})$ edges. In this section we show how to generalize the $+2$ subsetwise construction [31, 21] to the weighted setting by giving a construction which produces a subsetwise $+2W$ spanner of a weighted graph (with integer edge weights in $[1,W]$) on $O(nW\sqrt{|S|})$ edges. Due to space, we omit most proof details here but describe the construction instead.

A clustering $\mathcal{C}=\{C_{1},C_{2},\ldots,C_{q}\}$ is a set of disjoint subsets of vertices. Initially, every vertex is unclustered. The subsetwise $+2W$ construction has two steps: the clustering phase and the path buying phase. The clustering phase is exactly the same as that of [31, 21] in which we construct a cluster subgraph $G_{\mathcal{C}}$ as follows: set $\beta=\log_{n}\sqrt{|S|W}$, and while there is a vertex $v$ with at least $\lceil{n^{\beta}}\rceil$ unclustered neighbors, we add a cluster $C$ to $\mathcal{C}$ containing exactly $\lceil n^{\beta}\rceil$ unclustered neighbors of $v$ (note that $v\not\in C$). We add to $G_{\mathcal{C}}$ all edges $vx$ ($x\in C$) and $xy$ ($x,y\in C$). When there are no more vertices with at least $\lceil{n^{\beta}}\rceil$ unclustered neighbors, we add all the unclustered vertices and their incident edges to $G_{\mathcal{C}}$.

In the second (path-buying) phase, we start with a clustering $\mathcal{C}$ and a cluster subgraph $G_{0}:=G_{\mathcal{C}}$. There are $z:=\binom{|S|}{2}$ unordered pairs of vertices in $S$; let $\pi_{1}$, $\pi_{2}$, …, $\pi_{z}$ denote the shortest paths between these vertex pairs where $\pi_{i}=\pi(u_{i},v_{i})$ has endpoints $\{u_{i},v_{i}\}$. As in [21], we iterate from $i=1$ to $i=z$ and determine whether to add path $\pi_{i}$ to the spanner. Define the cost and value of a path $\pi_{i}$ as follows:

If $\text{cost}(\pi_{i})\leq(2W+1)\text{value}(\pi_{i})$, then we add (“buy”) $\pi_{i}$ to the spanner by letting $G_{i}=G_{i-1}\cup\pi_{i}$. Otherwise, we do not add $\pi_{i}$, and let $G_{i}=G_{i-1}$. The final spanner returned is $H=G_{z}$.

This follows from applying the $+8W$ construction of Ahmed et al. [3] (Appendix 3, Algorithm 3), except we use the above $+2W$ subsetwise spanner instead of the $+4W$ subsetwise spanner construction given in [3] as a subroutine.

Here, we provide pseudocode (Algorithms 1–3) describing the $+2W$, $+4W$, and $+8W$ pairwise spanner constructions²²2Using a tighter analysis or the above $+2W$ subsetwise construction in place of the $+4W$ construction in Algorithm 3, the additive error can be improved to $+2W(\cdot,\cdot)$, $+4W(\cdot,\cdot)$, and $+6W$ for integer edge weights. by Ahmed et al. [3]. These spanner constructions have a similar theme: first, construct a $d$-light initialization, which is a subgraph $H$ obtained by adding the $d$ lightest edges incident to each vertex (or all edges if the degree is at most $d$). Then for each pair $(s,t)\in P$, consider the number of edges in $\pi(s,t)$ which are absent in the current subgraph $H$. Add $\pi(s,t)$ to $H$ if the number of missing edges is at most some threshold $\ell$, or otherwise randomly sample vertices and either add a shortest path tree rooted at these vertices, or construct a subsetwise spanner among them.

Here we study a multi-level variant of graph spanners. We first define the problem:

Observe that Definition 4.1 generalizes the subsetwise spanner, which is a special case where $\ell=1$. We measure the size of a multi-level spanner by its sparsity, defined by $\text{sparsity}(\{G_{i}\}_{i=1}^{\ell}):=\sum_{i=1}^{\ell}|E(G_{i})|.$

The problem can equivalently be phrased in terms of priorities and rates: each vertex $v\in S_{1}$ has a priority $P(v)$ between 1 and $\ell$ (namely, $P(v)=\max\{i:v\in S_{i}\}$), and we wish to compute a single subgraph containing edges of different rates such that for all $u,v\in S_{1}$, there is a $+cW$ spanner path consisting of edges of rate at least $\min\{P(u),P(v)\}$. With this, we will typically refer to the priority of $v$ to denote the highest $i$ such that $v\in S_{i}$, or 0 if $v\not\in S_{1}$. In this section, we show that the multi-level version is not significantly harder than the ordinary “single-level” version: a subroutine which can compute an additive spanner can be used to compute a multi-level spanner whose sparsity is comparably good. Let OPT denote the minimum sparsity over all candidate multi-level additive spanners.

We first describe a simple rounding-up approach based on an algorithm by Charikar et al. [16] for the QoSMT problem, a similar generalization of the Steiner tree problem. For this approach, assume we have a subroutine which computes an exact or approximate single-level subsetwise spanner. Given $v\in S_{1}$, let $P(v)\in[1,\ell]$ denote the priority of $v$. The rounding-up approach is as follows: for each $v$, round $P(v)$ up to the nearest power of 2. This effectively constructs a “rounded-up” instance where all vertices in $S_{1}$ have priority either 1, 2, 4, …, $2^{\lceil\log_{2}\ell\rceil}$. The sparsity of the optimum solution in the rounded-up instance is at most $2\text{OPT}$; given the optimum solution to the original instance with sparsity OPT, a feasible solution to the rounded-up instance with sparsity at most $2\text{OPT}$ can be obtained by rounding up the rate of each edge to the nearest power of 2.

For each $i\in\{1,2,4,\ldots,2^{\lceil\log_{2}\ell\rceil}\}$, use the subroutine to compute a level-$i$ subsetwise spanner over all vertices whose rounded-up priority is at least $i$. The final multi-level additive spanner is obtained by taking the union of these computed spanners, by keeping an edge at the highest level it appears in.

This is proved using the same ideas as the $4\rho$-approximation for QoSMT [16]. As mentioned earlier, in practice we use an approximation algorithm to compute the subsetwise spanner instead of computing the minimum spanner.

This follows from using the $+2W$ subsetwise construction in Section 2. The approximation ratio of this subsetwise spanner algorithm is $O(nW/\sqrt{|S|})$ as the construction produces a spanner of size $O(nW\sqrt{|S|})$, while the sparsest additive spanner trivially has at least $|S|-1=\Omega(|S|)$ edges.

We now show that, under certain conditions, if we have a subroutine which computes a subsetwise spanner of $G$, $S$ of size $O(n^{a}|S|^{b})$ where $a$ and $b$ are absolute constants, a very naïve algorithm can be used to obtain a multi-level spanner also with sparsity $O(n^{a}|S_{1}|^{b})$.

The assumption that $|S_{i}|\leq\alpha|S_{i-1}|$ for some constant $\alpha$ is fairly natural, as many realistic networks tend to have significantly fewer hubs than non-hubs.

To compute a minimum size additive spanner, we utilize a slight modification of the ILP in [5, Section 9], wherein we choose the specific distortion function $f(t)=t+cW$ and minimize the sparsity rather than total weight of the spanner. For completeness, we present the full ILP for computing a single-level additive subsetwise spanner below along with a brief description of the multi-level extension. Here $E^{\prime}$ represents the bidirected edge set, obtained by adding directed edges $(u,v)$ and $(v,u)$ for each edge $uv\in E$. The binary variable $x_{(i,j)}^{uv}$ is 1 if edge $(i,j)$ is included on the selected $u$-$v$ path and 0 otherwise, and $w(e)$ is the weight of edge $e$.

Inequalities (3)–(4) enforce that for each $u$, $v\in S$, the selected edges corresponding to $u$, $v$ form a path; inequality (2) enforces that the length of this path is at most $\operatorname{dist}_{G}(u,v)+cW$ (note that $W$ may be replaced with $W(u,v)$). Inequality (5) ensures that if $x_{(i,j)}^{uv}=1$ or $x_{(i,j)}^{uv}=1$, then edge $ij$ is taken.

To generalize the ILP formulation to the multi-level problem, we take a similar set of variables for every level. The rest of the constraints are similar, except we define $x_{e}^{k}=1$ if edge $e$ is present on level $k$ and the variables $x_{(i,j)}^{uv}$ are also indexed by level. We add the constraint $x_{e}^{k}\leq x_{e}^{k-1}$ for all $k\in\{2,\ldots,\ell\}$ which enforces that if edge $e$ is present on level $k$, it is also present on all lower levels. Finally, the objective is to minimize the sparsity $\sum_{k=1}^{\ell}\sum_{e\in E}x_{e}^{k}$.

In this section, we provide experimental results involving the rounding-up framework described in Section 4. This framework needs a single level subroutine; we use the $+2W$ subsetwise construction in Section 2 and the three pairwise $+2W(\cdot,\cdot)$, $+4W(\cdot,\cdot)$, $+6W$ constructions provided in [3]³³3Note that, one can show that the $+2W$, $+4W$, $+8W$ spanners in [3] are actually $+2W(.,.),+4W(.,.)$ and $+6W$ spanners respectively by using a tighter analysis [4]. (see Appendix 3). We generate multi-level instances and solve the instances using our exact algorithm and the four approximation algorithms. We consider natural questions about how the number of levels $\ell$, number of vertices $n$, and decay rate of terminals with respect to levels affect the running times and (experimental) approximation ratios, defined as the sparsity of the returned multi-level spanner divided by OPT.

We used CPLEX 12.6.2 as an ILP solver in a high-performance computer for all experiments (Lenovo NeXtScale nx360 M5 system with 400 nodes). Each node has 192 GB of memory. We have used Python for implementing the algorithms and spanner constructions. Since we have run the experiment on a couple of thousand instances, we run the solver for four hours.

We have provided a framework where we can use different spanner subroutines to compute multi-level spanners of varying additive error. We additionally introduced a generalization of the $+2$ subsetwise spanner [21] to integer edge weights, and illustrate that this can reduce the $+8W$ error in [3] to $+6W$. A natural question is to provide an approximation algorithm that can handle different additive error for different levels. We also provided an ILP to find the exact solution for both global and local settings. Using the ILP and the given spanner constructions, we have run experiments and provided the experimental approximation ratio over the graphs we generated. The experimental results suggest that the $+2W$ clustering-based approach is slower than the initialization based approaches. We provided a method of changing the initialization parameter $d$ which reduces the sparsity in practice.