More Like this

1. Light Euclidean Steiner Spanners in the Plane

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

   Bhore, Sujoy; Toth, Csaba D. (June 2021, 37th International Symposium on Computational Geometry (SoCG 2021))

   null (Ed.)

   Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in ℝ^d. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on ε > 0 and d ∈ ℕ of the minimum lightness of a (1+ε)-spanner, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ≥ Ω(√n) is the spread of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness Õ(ε^{-(d+1)/2}) in dimensions d ≥ 3. Recently, Bhore and Tóth (2020) established a lower bound of Ω(ε^{-d/2}) for the lightness of Steiner (1+ε)-spanners in ℝ^d, for d ≥ 2. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions d ≥ 2. In this work, we show that for every finite set of points in the plane and every ε > 0, there exists a Euclidean Steiner (1+ε)-spanner of lightness O(ε^{-1}); this matches the lower bound for d = 2. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis. 

   more » « less
2. Minimum Weight Euclidean (1+ε)-Spanners

   Toth, Csaba D. (October 2022, Graph-Theoretic Concepts in Computer Science)

   Given a set S of n points in the plane and a parameter ε>0, a Euclidean (1+ε) -spanner is a geometric graph G=(S,E) that contains a path of weight at most (1+ε)∥pq∥2 for all p,q∈S . We show that the minimum weight of a Euclidean (1+ε)-spanner for n points in the unit square [0,1]2 is O(ε−3/2n−−√), and this bound is the best possible. The upper bound is based on a new spanner algorithm that sparsifies Yao-graphs. It improves upon the baseline O(ε−2n−−√), obtained by combining a tight bound for the weight of an MST and a tight bound for the lightness of Euclidean (1+ε)-spanners, which is the ratio of the spanner weight to the weight of the MST. The result generalizes to d-space for all d∈N : The minimum weight of a Euclidean (1+ε)-spanner for n points in the unit cube [0,1]d is Od(ε(1−d2)/dn(d−1)/d), and this bound is the best possible. For the n×n section of the integer lattice, we show that the minimum weight of a Euclidean (1+ε)-spanner is between Ω(ε−3/4n2) and O(ε−1log(ε−1)n2). These bounds become Ω(ε−3/4n−−√) and O(ε−1log(ε−1)n−−√) when scaled to a grid of n points in [0,1]2. . 

   more » « less
3. Online Spanners in Metric Spaces

   Bhore, Sujoy; Filtser, Arnold; Khodabandeh, Hadi; Toth, Csaba D. (September 2022, 30th Annual European Symposium on Algorithms (ESA 2022))

   Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner 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 t-spanner 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(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ 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 instance-optimal 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 = (2k-1)(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 trade-off 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
4. Online Spanners in Metric Spaces

   Bhore, Sujoy; Filtser, Arnold; Khodabandeh, Hadi; Toth, Csaba D. (September 2022, Proc. 30th Annual European Symposium on Algorithms (ESA))

   Given a metric space ℳ = (X,δ), a weighted graph G over X is a metric t-spanner 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 t-spanner 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(ε^{1-d}log ε^{-1})⋅ n edges, almost matching the (offline) optimal bound of O_d(ε^{1-d})⋅ 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 instance-optimal 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 = (2k-1)(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 trade-off 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
5. Space Complexity of Minimum Cut Problems in Single-Pass Streams

   https://doi.org/10.4230/LIPIcs.ITCS.2025.43  

   Ding, Matthew; Garces, Alexandro; Li, Jason; Lin, Honghao; Nelson, Jelani; Shah, Vihan; Woodruff, David P (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the specific application of finding minimum cuts in streams is less well-studied. To this end, we show upper and lower bounds on minimum cut problems in insertion-only streams for a variety of settings, including for both randomized and deterministic algorithms, for both arbitrary and random order streams, and for both approximate and exact algorithms. One of our main results is an Õ(n/ε) space algorithm with fast update time for approximating a spectral cut query with high probability on a stream given in an arbitrary order. Our result breaks the Ω(n/ε²) space lower bound required of a sparsifier that approximates all cuts simultaneously. Using this result, we provide streaming algorithms with near optimal space of Õ(n/ε) for minimum cut and approximate all-pairs effective resistances, with matching space lower-bounds. The amortized update time of our algorithms is Õ(1), provided that the number of edges in the input graph is at least (n/ε²)^{1+o(1)}. We also give a generic way of incorporating sketching into a recursive contraction algorithm to improve the post-processing time of our algorithms. In addition to these results, we give a random-order streaming algorithm that computes the exact minimum cut on a simple, unweighted graph using Õ(n) space. Finally, we give an Ω(n/ε²) space lower bound for deterministic minimum cut algorithms which matches the best-known upper bound up to polylogarithmic factors. 

   more » « less