More Like this

1. Sometimes Reliable Spanners of Almost Linear Size

   Buchin, Kevin ; Har-Peled, Sariel ; Olah, Daniel ( January 2020 , 28th Annual European Symposium on Algorithms (ESA))

   Grandoni, Fabrizio ; Herman, Grzegorz ; Sanders, Peter (Ed.)

   Reliable spanners can withstand huge failures, even when a linear number of vertices are deleted from the network. In case of failures, some of the remaining vertices of a reliable spanner may no longer admit the spanner property, but this collateral damage is bounded by a fraction of the size of the attack. It is known that Ω(nlog n) edges are needed to achieve this strong property, where n is the number of vertices in the network, even in one dimension. Constructions of reliable geometric (1+ε)-spanners, for n points in ℝ^d, are known, where the resulting graph has 𝒪(n log n log log⁶n) edges. Here, we show randomized constructions of smaller size spanners that have the desired reliability property in expectation or with good probability. The new construction is simple, and potentially practical - replacing a hierarchical usage of expanders (which renders the previous constructions impractical) by a simple skip list like construction. This results in a 1-spanner, on the line, that has linear number of edges. Using this, we present a construction of a reliable spanner in ℝ^d with 𝒪(n log log²n log log log n) edges. 

   more » « less
2. Weighted Additive Spanners

   https://doi.org/10.1007/978-3-030-60440-0_32  

   Ahmed, R ; Bodwin, G ; Darabi, F ; Kobourov, S ; Spence, R ( October 2020 , 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG))

   A spanner of a graph G is a subgraph H that approximately preserves shortest path distances in G. Spanners are commonly applied to compress computation on metric spaces corresponding to weighted input graphs. Classic spanner constructions can seamlessly handle edge weights, so long as error is measured multiplicatively. In this work, we investigate whether one can similarly extend constructions of spanners with purely additive error to weighted graphs. These extensions are not immediate, due to a key lemma about the size of shortest path neighborhoods that fails for weighted graphs. Despite this, we recover a suitable amortized version, which lets us prove direct extensions of classic +2 and +4 unweighted spanners (both all-pairs and pairwise) to +2W and +4W weighted spanners, where W is the maximum edge weight. Specifically, we show that a weighted graph G contains all-pairs (pairwise) +2W and +4W weighted spanners of size O(n3/2) and O(n7/5) (O(np1/3) and O(np2/7)) respectively. For a technical reason, the +6 unweighted spanner becomes a +8W weighted spanner; closing this error gap is an interesting remaining open problem. That is, we show that G contains all-pairs (pairwise) +8W weighted spanners of size O(n4/3) (O(np1/4)). 

   more » « less
3. Local Computation Algorithms for Spanners

   Parter, Merav ; Rubinfeld, Ronitt ; Vakilian, Ali ; Yodpinyanee, Anak ( January 2019 , Innovations in Theoretical Computer Science (ITCS))

   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 best-known existential size-stretch trade-off 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 n-vertex 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 n-vertex 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 [Lenzen-Levi, 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
4. Constant-hop spanners for more geometric intersection graphs, with even smaller size

   https://doi.org/10.4230/LIPIcs.SoCG.2023.23  

   Chan, Timothy M. ; Huang, Zhengcheng ( June 2023 , Proc. 39th International Symposium on Computational Geometry (SoCG 2023))

   Chambers, Erin W. ; Gudmundsson, Joachim (Ed.)

   In SoCG 2022, Conroy and Tóth presented several constructions of sparse, low-hop spanners in geometric intersection graphs, including an O(nlog n)-size 3-hop spanner for n disks (or fat convex objects) in the plane, and an O(nlog² n)-size 3-hop spanner for n axis-aligned 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 near-linear size be achieved for more general classes of intersection graphs? We address both questions simultaneously, by presenting new constructions of constant-hop 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 k-th function in the inverse Ackermann hierarchy. We similarly prove the existence of an O(1)-hop spanner for intersection graphs of d-dimensional 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 2-hop spanner for disks (or more generally objects with linear union complexity) in the plane, and an O(nlog n)-size 3-hop spanner for axis-aligned rectangles in the plane. Our proofs are all simple, using separator theorems, recursion, shifted quadtrees, and shallow cuttings. 

   more » « less
5. Improved Local Computation Algorithms for Constructing Spanners

   Arviv, Ruby ; Chung, Lily ; Levi, Reut ; Pyne, Edward ( September 2023 , Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023)

   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 (2r-1)-spanners with Õ(n^{1+1/r}) edges and probe complexity of Õ(n^{1-1/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 3-spanner, is optimal up to polylogarithmic factors. Our result improves over the probe complexity of Parter et al. (ITCS 2019) that is Õ(n^{1-1/2r}) for r ∈ {2,3}. Both our algorithms and the algorithms of Parter et al. use a combination of neighbor-probes and pair-probes in the above-mentioned 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}Δ²) neighbor-probes, 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