Given a weighted graph @math and @math , a subgraph @math is a of @math if the lengths of shortest paths in @math are preserved in @math up to a multiplicative factor of @math . The problem aims to preserve distances in @math for only a subset of the vertices. We generalize the minimum-cost subsetwise spanner problem to one where vertices appear on multiple levels, which we call the (MLGS) problem, and describe two simple heuristics. Applications of this problem include road network building and multi-level graph visualization, especially where vertices may require different grades of service. We formulate a 0--1 integer linear program (ILP) of size @math for the more general minimum , which resolves an open question by Sigurd and Zachariasen on whether this problem admits a useful polynomial-size ILP. We extend this ILP formulation to the MLGS problem, and evaluate the heuristic and ILP performance on random graphs of up to 100 vertices and 500 edges.
Spanners and variants thereof have been studied for at least three decades, so we focus on results relating to pairwise or subsetwise spanners. Alth " o @cite_22 provide a simple greedy algorithm that constructs a multiplicative @math --spanner given a graph @math and a real number @math . The greedy algorithm sorts edges in @math by nondecreasing weight, then for each @math , computes the shortest path @math from @math to @math in the current spanner, and adds the edge to the spanner if the weight of @math is greater than @math . The resulting subgraph @math is a @math --spanner for @math . The main result of @cite_22 is that, given a weighted graph @math and @math , there is a greedy @math --spanner @math containing at most @math edges, and whose weight is at most @math where @math denotes the weight of a minimum spanning tree of @math .
@cite_22
2949196298 2951859740 1525064252 2099237198
The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it is at least as good as any other spanner construction, in terms of both the size and weight parameters. However, a rigorous proof for this statement has remained elusive. In this work we fill in the theoretical gap via a surprisingly simple observation: The greedy spanner is (or existentially near-optimal) for several important graph families. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs (due to Chechik and Wulff-Nilsen [SODA'16]) and doubling metrics (due to Gottlieb [FOCS'15]) are complex. Plugging our observation on these results, we conclude that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Further, we observe that approximate-greedy algorithms are existentially near-optimal as well. Consequently, we provide an @math -time construction of @math -spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is @math and whose number of edges and degree are unbounded, and remarkably, it matches the state-of-the-art Euclidean result (due to [SICOMP'02]) in all the involved parameters (up to dependencies on @math and the dimension). Given an undirected @math -node unweighted graph @math , a spanner with stretch function @math is a subgraph @math such that, if two nodes are at distance @math in @math , then they are at distance at most @math in @math . Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the @math - @math distance only for pairs @math in a given set @math . Such @math -spanners were studied before [Coppersmith,Elkin'05] only in the special case that @math is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same @math ) and of the best known spanners (with the same @math ). In more detail, for arbitrary @math , we show that there exists a @math -spanner of size @math with @math . Alternatively, for any @math , there exists a @math -spanner of size @math with @math . We also consider the relevant special case that there is a critical set of nodes @math , and we wish to approximate either the distances within nodes in @math or from nodes in @math to any other node. We show that there exists an @math -spanner of size @math with @math , and an @math -spanner of size @math with @math . All the mentioned pairwise spanners can be constructed in polynomial time. Spanners are sparse subgraphs that preserve distances up to a given factor in the underlying graph. Recently spanners have found important practical applications in metric space searching and message distribution in networks. These applications use some variant of the so-called greedy algorithm for constructing the spanner — an algorithm that mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners have nice theoretical properties, but their practical performance with respect to total weight is unknown. In this paper we give an exact algorithm for constructing minimum-weight spanners in arbitrary graphs. By using the solutions (and lower bounds) from this algorithm, we experimentally evaluate the performance of the greedy algorithm for a set of realistic problem instances. An (α, β)-spanner of an unweighted graph G is a subgraph H that distorts distances in G up to a multiplicative factor of α and an additive term β. It is well known that any graph contains a (multiplicative) (2k−1, 0)-spanner of size O(n1+1 k) and an (additive) (1,2)-spanner of size O(n3 2). However no other additive spanners are known to exist. In this article we develop a couple of new techniques for constructing (α, β)-spanners. Our first result is an additive (1,6)-spanner of size O(n4 3). The construction algorithm can be understood as an economical agent that assigns costs and values to paths in the graph, purchasing affordable paths and ignoring expensive ones, which are intuitively well approximated by paths already purchased. We show that this path buying algorithm can be parameterized in different ways to yield other sparseness-distortion tradeoffs. Our second result addresses the problem of which (α, β)-spanners can be computed efficiently, ideally in linear time. We show that, for any k, a (k,k−1)-spanner with size O(kn1+1 k) can be found in linear time, and, further, that in a distributed network the algorithm terminates in a constant number of rounds. Previous spanner constructions with similar performance had roughly twice the multiplicative distortion.