A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every k, a spanner with size O(n^{1+1/k}) and stretch (2k+1) can be constructed by a simple centralized greedy algorithm, and this is tight assuming Erdős girth conjecture. In this paper we study the problem of constructing spanners in a local manner, specifically in the Local Computation Model proposed by Rubinfeld et al. (ICS 2011). We provide a randomized Local Computation Agorithm (LCA) for constructing (2r1)spanners with Õ(n^{1+1/r}) edges and probe complexity of Õ(n^{11/r}) for r ∈ {2,3}, where n denotes the number of vertices in the input graph. Up to polylogarithmic factors, in both cases, the stretch factor is optimal (for the respective number of edges). In addition, our probe complexity for r = 2, i.e., for constructing a 3spanner, is optimal up to polylogarithmic factors. Our result improves over the probe complexity of Parter et al. (ITCS 2019) that is Õ(n^{11/2r}) for r ∈ {2,3}. Both our algorithms and the algorithms of Parter et al. use a combination of neighborprobes and pairprobes in the abovementioned LCAs. For general k ≥ 1, we provide an LCA for constructing O(k²)spanners with Õ(n^{1+1/k}) edges using O(n^{2/3}Δ²) neighborprobes, improving over the Õ(n^{2/3}Δ⁴) algorithm of Parter et al. By developing a new randomized LCA for graph decomposition, we further improve the probe complexity of the latter task to be O(n^{2/3(1.5α)/k}Δ²), for any constant α > 0. This latter LCA may be of independent interest.
more »
« less
Local Computation Algorithms for Spanners
A graph spanner is a fundamental graph structure that faithfully preserves the pairwise distances in the input graph up to a small multiplicative stretch. The common objective in the computation of spanners is to achieve the bestknown existential sizestretch tradeoff efficiently.
Classical models and algorithmic analysis of graph spanners essentially assume that the algorithm can read the input graph, construct the desired spanner, and write the answer to the output tape. However, when considering massive graphs containing millions or even billions of nodes not only the input graph, but also the output spanner might be too large for a single processor to store.
To tackle this challenge, we initiate the study of local computation algorithms (LCAs) for graph spanners in general graphs, where the algorithm should locally decide whether a given edge (u,v)∈E belongs to the output spanner. Such LCAs give the user the `illusion' that a specific sparse spanner for the graph is maintained, without ever fully computing it. We present the following results:
For general nvertex graphs and r∈{2,3}, there exists an LCA for (2r−1)spanners with O˜(n1+1/r) edges and sublinear probe complexity of O˜(n1−1/2r). These size/stretch tradeoffs are best possible (up to polylogarithmic factors).
For every k≥1 and nvertex graph with maximum degree Δ, there exists an LCA for O(k2) spanners with O˜(n1+1/k) edges, probe complexity of O˜(Δ4n2/3), and random seed of size polylog(n). This improves upon, and extends the work of [LenzenLevi, 2018].
We also complement our results by providing a polynomial lower bound on the probe complexity of LCAs for graph spanners that holds even for the simpler task of computing a sparse connected subgraph with o(m) edges.
more »
« less
 NSFPAR ID:
 10108397
 Date Published:
 Journal Name:
 Innovations in Theoretical Computer Science (ITCS)
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)Recent work has pinned down the existentially optimal size bounds for vertex faulttolerant spanners: for any positive integer k, every nnode graph has a (2k – 1)spanner on O(f^{1–1/k} n^{1+1/k}) edges resilient to f vertex faults, and there are examples of input graphs on which this bound cannot be improved. However, these proofs work by analyzing the output spanner of a certain exponentialtime greedy algorithm. In this work, we give the first algorithm that produces vertex fault tolerant spanners of optimal size and which runs in polynomial time. Specifically, we give a randomized algorithm which takes Õ(f^{1–1/k} n^{2+1/k} + mf2) time. We also derandomize our algorithm to give a deterministic algorithm with similar bounds. This reflects an exponential improvement in runtime over [BodwinPatel PODC '19], the only previously known algorithm for constructing optimal vertex faulttolerant spanners.more » « less

Chambers, Erin W. ; Gudmundsson, Joachim (Ed.)In SoCG 2022, Conroy and Tóth presented several constructions of sparse, lowhop spanners in geometric intersection graphs, including an O(nlog n)size 3hop spanner for n disks (or fat convex objects) in the plane, and an O(nlog² n)size 3hop spanner for n axisaligned rectangles in the plane. Their work left open two major questions: (i) can the size be made closer to linear by allowing larger constant stretch? and (ii) can nearlinear size be achieved for more general classes of intersection graphs? We address both questions simultaneously, by presenting new constructions of constanthop spanners that have almost linear size and that hold for a much larger class of intersection graphs. More precisely, we prove the existence of an O(1)hop spanner for arbitrary string graphs with O(nα_k(n)) size for any constant k, where α_k(n) denotes the kth function in the inverse Ackermann hierarchy. We similarly prove the existence of an O(1)hop spanner for intersection graphs of ddimensional fat objects with O(nα_k(n)) size for any constant k and d. We also improve on some of Conroy and Tóth’s specific previous results, in either the number of hops or the size: we describe an O(nlog n)size 2hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an O(nlog n)size 3hop spanner for axisaligned rectangles in the plane. Our proofs are all simple, using separator theorems, recursion, shifted quadtrees, and shallow cuttings.more » « less

Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing largescale graphs. By now, we have quite fast algorithmsusually sublogarithmictime and often poly(łogłog n)time, or even fasterfor a number of fundamental graph problems in the massively parallel computation (MPC) model. This model is a widelyadopted theoretical abstraction of MapReduce style settings, where a number of machines communicate in an alltoall manner to process largescale data. Contributing to this line of work on MPC graph algorithms, we present poly(łog k) ε poly(łogłog n) round MPC algorithms for computing O(k^1+o(1) )spanners in the strongly sublinear regime of local memory. To the best of our knowledge, these are the first sublogarithmictime MPC algorithms for spanner construction. As primary applications of our spanners, we get two important implications, as follows: For the MPC setting, we get an O(łog^2łog n)round algorithm for O(łog^1+o(1) n) approximation of all pairs shortest paths (APSP) in the nearlinear regime of local memory. To the best of our knowledge, this is the first sublogarithmictime MPC algorithm for distance approximations. Our result above also extends to the Congested Clique model of distributed computing, with the same round complexity and approximation guarantee. This gives the first sublogarithmic algorithm for approximating APSP in weighted graphs in the Congested Clique model.more » « less

Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric tspanner of ℳ if for every u,v ∈ X, δ(u,v) ≤ δ_G(u,v) ≤ t⋅ δ(u,v), where δ_G is the shortest path metric in G. In this paper, we construct spanners for finite sets in metric spaces in the online setting. Here, we are given a sequence of points (s₁, …, s_n), where the points are presented one at a time (i.e., after i steps, we have seen S_i = {s₁, … , s_i}). The algorithm is allowed to add edges to the spanner when a new point arrives, however, it is not allowed to remove any edge from the spanner. The goal is to maintain a tspanner G_i for S_i for all i, while minimizing the number of edges, and their total weight. Under the L₂norm in ℝ^d for arbitrary constant d ∈ ℕ, we present an online (1+ε)spanner algorithm with competitive ratio O_d(ε^{d} log n), improving the previous bound of O_d(ε^{(d+1)}log n). Moreover, the spanner maintained by the algorithm has O_d(ε^{1d}log ε^{1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1d})⋅ n. In the plane, a tighter analysis of the same algorithm provides an almost quadratic improvement of the competitive ratio to O(ε^{3/2}logε^{1}log n), by comparing the online spanner with an instanceoptimal spanner directly, bypassing the comparison to an MST (i.e., lightness). As a counterpart, we design a sequence of points that yields a Ω_d(ε^{d}) lower bound for the competitive ratio for online (1+ε)spanner algorithms in ℝ^d under the L₁norm. Then we turn our attention to online spanners in general metrics. Note that, it is not possible to obtain a spanner with stretch less than 3 with a subquadratic number of edges, even in the offline setting, for general metrics. We analyze an online version of the celebrated greedy spanner algorithm, dubbed ordered greedy. With stretch factor t = (2k1)(1+ε) for k ≥ 2 and ε ∈ (0,1), we show that it maintains a spanner with O(ε^{1}logε^{1})⋅ n^{1+1/k} edges and O(ε^{1}n^{1/k}log² n) lightness for a sequence of n points in a metric space. We show that these bounds cannot be significantly improved, by introducing an instance that achieves an Ω(1/k⋅ n^{1/k}) competitive ratio on both sparsity and lightness. Furthermore, we establish the tradeoff among stretch, number of edges and lightness for points in ultrametrics, showing that one can maintain a (2+ε)spanner for ultrametrics with O(ε^{1}logε^{1})⋅ n edges and O(ε^{2}) lightness.more » « less