Subsetwise and Multi-Level Additive Spanners with Lightness Guarantees

Given a graph $G$, a spanner of $G$ is a subgraph that preserves lengths of shortest paths in $G$ up to some multiplicative or additive error [26, 25]. A subgraph $H=(V,E^{\prime}\subseteq E)$ of $G$ is called a multiplicative $\alpha$–spanner if the lengths of shortest paths in $G$ are preserved in $H$ up to a multiplicative factor of $\alpha$, that is, $d_{H}(u,v)\leq\alpha\cdot d_{G}(u,v)$ for all $u,v\in V$, where $d_{G}(u,v)$ denotes the length of the shortest path from $u$ to $v$ in $G$. For being an additive +$\beta$ spanner, $H$ must satisfy the inequality $d_{H}(u,v)\leq d_{G}(u,v)+\beta$.

Multiplicative spanners were introduced by Peleg and Schäffer [26] in 1989. Since then a rich body of research has attempted to find sparse and lightweight spanners on unweighted graphs. Such spanners find applications in computing graph summaries, building distributed computing models, and designing communication networks [7, 3]. Finding a multiplicative $\alpha$–spanner with $m$ or fewer edges is NP–hard [26]. It is also NP–hard to find a $c\log|V|$-approximate solution where $c<1$, even for bipartite graphs [23]. However, every $n$-vertex graph admits a multiplicative $(2k-1)$-spanner with $O(n^{1+1/k})$ edges and $O(n/k)$ lightness [6], which has been improved in subsequent research [19, 18, 14, 11, 24].

A multiplicative factor allows for larger distances in a spanner, especially for pairs that have larger graph distances. Therefore, an additive spanner is sometimes more desirable even with the cost of having a larger number of edges. For unweighted graphs, there exist additive $+2,+4$ and $+6$ spanners with $O(n^{3/2})$ [5, 22], $\tilde{O}(n^{7/5})$ [13] and $O(n^{4/3})$ edges [9, 22], respectively, whereas any additive $+n^{o(1)}$ spanners requires $\Omega(n^{4/3-\epsilon})$ edges [1]. Here $\tilde{O}()$ hides polylogarithmic factors. These results have been extended to weighted graphs with the additive factors $+\beta W_{G}(\cdot,\cdot)$, where $W_{G}(\cdot,\cdot)$ represents the maximum weight on a shortest path between $u$ and $v$ in $G$, i.e., $d_{H}(u,v)\leq d_{G}(u,v)+\beta W_{G}(u,v)$. We use $W(u,v)$ instead of $W_{G}(u,v)$ if the graph $G$ is clear from context. Specifically, there exist additive $+2W(\cdot,\cdot),+4W(\cdot,\cdot)$ and $+(6+\epsilon)W(\cdot,\cdot)$ spanners of size $O(n^{3/2})$ [16], $\tilde{O}(n^{7/5})$ [3] and $O_{\epsilon}(n^{4/3})$ [17], respectively, where $O_{\epsilon}()$ hides $poly(1/\epsilon)$ factors. Researchers have also attempted to guarantee a good lightness bound for such spanners, where the lightness is the ratio of the spanner weight to the weight of a minimum spanning tree of $G$. So far, non-trivial lightness guarantees have been obtained only for (all-pairs) additive $+\epsilon W(\cdot,\cdot)$ and $+(4+\epsilon)W(\cdot,\cdot)$ spanners, where the lightness bounds are $O_{\epsilon}(n)$ and $O_{\epsilon}(n^{2/3})$, respectively [2].

Real-life graphs can be very large, which motivates computing a subgraph that approximately preserves the shortest path distances among a subset of important vertices. Subsetwise spanner (also known as terminal spanners [15, 8]) is another commonly studied version, where in addition to $G$, the input consists of a vertex subset $S$ of $G$, known as terminals. The goal is to compute an additive or multiplicative spanner that guarantees that for every $u,v\in S$, $d_{H}(u,v)$ is within an additive or multiplicative factor of $d_{G}(u,v)$. Computing a subsetwise spanner comes with additional challenges, e.g., consider computing a minimum spanning tree vs. a minimum Steiner tree for an analogy. There exist additive $+2$ and additive $+(2+\epsilon)W(\cdot,\cdot)$ subsetwise spanners with size $O(n\sqrt{|S|})$ and $O_{\epsilon}(n\sqrt{|S|})$, respectively [3], however they do not come with any non-trivial lightness guarantees. The algorithms that construct such spanners often follow a greedy construction framework, i.e., they construct an initial graph and then examine the pairs in sorted nondecreasing order of the maximum weight, i.e., $W(\cdot,\cdot)$. For each pair $(u,v)$, if it still fails to satisfy the distance condition of an additive spanner, then all the edges on the corresponding shortest path are added to the spanner.

In this paper, we focus on computing subsetwise additive spanners that are also light with respect to a Steiner tree $T$. To this end, we define subset-lightness. Specifically, let $P\subseteq S\times S$ be the pairs that do not satisfy the spanner condition in a minimum Steiner tree $R$ with terminal set $S$. Let $T$ be a minimum Steiner tree with terminal set $(S\cup S^{*})$, where $S^{*}$ is the set of vertices on the shortest paths of the pairs in $P$. Then, the subset-lightness is the ratio of the spanner weight to the weight of the minimum Steiner tree $T$. Although it may initially appear that $R$ could be a simpler choice over $T$ when defining lightness for subsetwise spanners, $R$ may be a very loose lower bound. For example, consider a $2n$-vertex complete graph $G$ with vertex set $S$ and let $A,B$ be a partition of $S$ into equal-size subsets. Assume that the weight of each edge that is crossing the partition is $2$ and the weight of each remaining edge is $(2+\delta)$, where $\delta>0$. A minimum spanning tree $M$ of $G$ is a star graph with weight $O(n)$. Let $G^{\prime}$ be a graph obtained by subdividing each edge of $G$ once and distributing the weight of the edge equally among the two new edges. It is straightforward to verify that $M$ determines a minimum Steiner tree $R$ in $G^{\prime}$ with terminal set $S$. Consider a pair $a,b$, where $a\in A$, $b\in B$ and the edge $(a,b)$ does not belong to $R$. Then the weight of the shortest path $a,\ldots,b$ in $R$ is $4+\delta>4$ and thus does not satisfy the distance condition for a $+2$ spanner. There are $\Omega(n^{2})$ pairs with one element in $A$ and the other in $B$, and any +2 spanner must take all these shortest paths. Therefore, the ratio of a +2 spanner over the weight of $R$ would be very large, i.e., $\Omega(|S|)$, whereas $T$ (i.e., a minimum Steiner tree with terminals $(S\cup S^{*})$) is a better lower bound and gives a constant ratio. Therefore, we use $T$ to define subset-lightness.

The definition of subset-lightness naturally extends to the general case, i.e., when $|S|=n$, where a minimum Steiner tree coincides with a minimum spanning tree. However, the techniques used to compute all-pairs additive spanners do not generalize to subsetwise additive spanners [2]. Therefore, a natural question is whether we can compute subsetwise spanners with non-trivial guarantees on subset-lightness, and in this paper, we answer this question affirmatively.

Notice that the results of Theorem 2.1 and Theorem 2.2 exactly match the bounds provided for all-pairs spanners [2] if we set $S=V$. Hence, our results are not only answering stronger questions, but they are also directly comparable with the existing results. The main challenge to generalizing the all-pairs results to subsetwise results is that the former compares against the minimum spanning tree. A counting argument that is often used in additive spanner constructions is based on the number of improvements, i.e., the number of improvements that may occur for all pairs of vertices is no more than an upper bound. Here, an improvement means that the difference in the shortest path between the pair before and after adding a set of edges is non-zero. However, this idea does not work in the subsetwise setting if we only compute a Steiner tree that spans $S$. A key contribution of our work is that we address this problem by computing Steiner trees that not only span $S$ but also the vertices in the shortest paths of some vertex pairs from $S$.

We next consider computing multi-level (multiplicative/additive) spanner, where the goal is to compute a hierarchy of (multiplicative/additive) spanners that minimizes the total number of edges or the total edge weight of all the spanners. Specifically, the input consists of a graph and some subsets $S_{1},S_{2},\ldots,S_{k}$ of its vertices where $S_{1}\subseteq S_{2}\subseteq\ldots\subseteq S_{k}$. The goal is to find a hierarchy of spanners such that the spanner at the $i$th level connects $S_{i}$ and for $i>2$, the spanner $S_{i}$ includes the edges of the spanners $S_{1},\ldots,S_{i-1}$. Multi-level spanners can model real-world scenarios where different levels of importance are assigned to different sets of vertices. Examples of such scenarios include modeling the quality of service requirements for the nodes in communication networks [12], or visualizing a graph on a map when the details are revealed as the users zoom in [20]. There exists a 4-approximation algorithm for this problem [4], and we give an improved $e$-approximation (Theorem 3.1).

The rest of the paper is organized as follows. Section 2 discusses the results on lightweight additive spanners. Section 3 presents the $e$-approximation algorithm for multilevel spanners. Finally, Section 4 concludes the paper with directions for future research.

In this section, we give our results on additive and lightweight spanners. All the spanners that we construct rely on the following preliminary setup.