It is known that any n-point set in the d-dimensional Euclidean space ℝ^d, for d = O(1), admits: 1) A (1+ε)-spanner with maximum degree Õ(ε^{-d+1}) and with lightness Õ(ε^{-d}), for any ε > 0. 2) A (1+ε)-tree cover with Õ(n ⋅ ε^{-d+1}) trees and maximum degree of O(1) in each tree. Moreover, all the parameters in these constructions are optimal: For any 2 ≤ d = O(1), there exists an n-point set in ℝ^d, for which any (1+ε)-spanner has Ω̃(n⋅ε^{-d+1}) edges and lightness Ω̃(ε^{-d}). The upper bounds for Euclidean spanners rely heavily on the spatial property of cone partitioning in ℝ^d, which does not seem to extend to the wider family of doubling metrics, i.e., metric spaces of constant doubling dimension. In doubling metrics, a simple spanner construction from two decades ago, the net-tree spanner, has Õ(n⋅ε^{-d}) edges, and it could be transformed into a spanner of maximum degree Õ(ε^{-d}) and lightness Õ(n⋅ε^{-(d+1)}) by pruning redundant edges. Moreover, a careful refinement of the net-tree spanner yields a (1+ε)-tree cover with Õ(ε^{-d}) trees. Despite a large body of work, the problem of obtaining tight bounds for spanners and tree covers in the wider family of doubling metrics has remained elusive. We resolve this problem by presenting: 1) A surprisingly simple and tight lower bound, which shows that the net-tree spanner and its pruned version are optimal with respect to all the involved parameters. 2) A new construction of (1+ε)-tree covers with Õ(n⋅ε^{-d}) trees, with maximum degree O(1) in each tree. This construction is optimal with respect to the number of trees and maximum degree.

Sparse shortcuttings of trees - equivalently, sparse 1-spanners for tree metrics with bounded hop-diameter - have been studied extensively (under different names and settings), since the pioneering works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994], initially motivated by applications to range queries, online tree product, and MST verification, to name a few. These constructions were also lifted from trees to other graph families using known low-distortion embedding results. The works of [Andrew Chi-Chih Yao, 1982; Chazelle, 1987; Noga Alon and Baruch Schieber, 1987; Hans L. Bodlaender et al., 1994] establish a tight tradeoff between hop-diameter and sparsity (or average degree) for tree shortcuttings and imply constant-hop shortcuttings for n-node trees with sparsity O(log^* n). Despite their small sparsity, all known constant-hop shortcuttings contain dense subgraphs (of sparsity Ω(log n)), which is a significant drawback for many applications. We initiate a systematic study of constant-hop tree shortcuttings that are "tree-like". We focus on two well-studied graph parameters that measure how far a graph is from a tree: arboricity and treewidth. Our contribution is twofold. - New upper and lower bounds for tree-like shortcuttings of trees, including an optimal tradeoff between hop-diameter and treewidth for all hop-diameter up to O(log log n). We also provide a lower bound for larger values of k, which together yield hop-diameter× treewidth = Ω((log log n)²) for all values of hop-diameter, resolving an open question of [Arnold Filtser and Hung Le, 2022; H. Le, 2023]. - Applications of these bounds, focusing on low-dimensional Euclidean and doubling metrics. A seminal work of Arya et al. [S. Arya et al., 1995] presented a (1+ε)-spanner with constant hop-diameter and sparsity O(log^* n), but with large arboricity. We show that constant hop-diameter is sufficient to achieve arboricity O(log^*{n}). Furthermore, we present a (1+ε)-stretch routing scheme in the fixed-port model with 3 hops and a local memory of O(log²n / log log n) bits, resolving an open question of [Omri Kahalon et al., 2022].

For a weighted graph $G = (V, E, w)$ and a designated source vertex $s \in V$, a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an $(α, β)$-SLT of $G$ w.r.t. $s \in V$ is a spanning tree of $G$ with root-stretch $α$ (preserving all distances between $s$ and the other vertices up to a factor of $α$) and lightness $β$ (its weight is at most $β$ times the weight of a minimum spanning tree of $G$). Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards this question by presenting two bicriteria approximation algorithms. For any $ε>0$, a set $P$ of $n$ points in constant-dimensional Euclidean space and a source $s\in P$, our first (respectively, second) algorithm returns, in $O(n \log n \cdot {\rm polylog}(1/ε))$ time, a non-Steiner (resp., Steiner) tree with root-stretch $1+O(ε\log ε^{-1})$ and weight at most $O(\mathrm{opt}_ε\cdot \log^2 ε^{-1})$ (resp., $O(\mathrm{opt}_ε\cdot \log ε^{-1})$), where $\mathrm{opt}_ε$ denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch $1+ε$.

In the dynamic minimum dominating set (MDS) problem, the goal is to efficiently maintain an approximate MDS in an n-vertex graph with vertex costs in [1/C,1] undergoing edge insertions and deletions. In STACS'19 [Niklas Hjuler et al., 2019] it was shown that an O(log n)-approximate MDS can be maintained in unweighted graphs with O(Δ ⋅ log n) update time, where Δ is an upper bound on the maximum degree throughout the update sequence, and in STOC'23 [Solomon and Uzrad, 2023] this was extended to weighted graphs and improves the approximation guarantee to (1+ε)ln Δ. Is it possible to achieve poly(log n) update time without any dependence on Δ, for any nontrivial graph family? This basic question has remained open even in forests and even for unweighted instances. The arboricity α = α(G) of a graph G is the minimum number of edge-disjoint forests whose union is G, and is a standard measure of sparsity. While α is bounded by Δ in any graph, various real-world graph families exhibit a significant gap between α and Δ. In this work, we show that one can maintain an O(α)-approximate MDS with update time O(α⋅log(Cn)), for dynamic graphs whose arboricity is bounded by α throughout the update sequence. This replaces the dependence on Δ in prior update bounds with α, while also improving the approximation guarantee for bounded-arboricity graphs. In particular, for any graph family of constant arboricity, such as planar graphs, bounded treewidth graphs, and more generally graphs excluding a fixed minor, our algorithm gives an O(1)-approximation with O(log (Cn)) update time. To achieve this result, our algorithm departs from prior greedy-based approaches, relying instead on the primal-dual framework and new structural insights specific to bounded arboricity graphs.

In the dynamic set cover (SC) problem, the input is a dynamic universe of at most n elements and a fixed collection of m sets, where each element belongs to at most f sets and each set has a cost in [1/C,1]. The objective is to efficiently maintain an approximate minimum SC under element updates. Efficiency is primarily measured by the update time, but another important parameter is the recourse (the number of changes to solution per update). Ideally, one would like to achieve low worst-case bounds on both update time and recourse. One can achieve an approximation of (1+ε)ln n (greedy-based) or (1+ε)f (primal–dual-based) with worst-case update time O(f log n) (ignoring ε-dependencies). However, despite a large body of work, no algorithm with low update time (even amortized) and nontrivial worst-case recourse is known even for unweighted instances (C = 1)! We remedy this by providing a transformation that, given a SC algorithm with approximation α and update time T as a black-box, returns a set cover algorithm with approximation (2 + ε)α, update time O(T + α C) and worst-case recourse O(α C). Our main results are obtained by leveraging this transformation for constant C: - For f = O(log n), applying the transformation on the best primal-dual-based algorithm yields worst-case recourse O(f). For constant f (e.g., vertex cover), we get near-optimal bounds on all parameters. - For f = Ω(log n), applying the transformation on the best greedy-based algorithm yields worst-case recourse O(log n). As our main technical contribution, we show that by opening the black box and exploiting a certain robustness property of the greedy-based algorithm, the worst-case recourse can be reduced to O(1), without sacrificing the other parameters, yielding a ((2 + ε) ln n)-approximation with worst-case update time O(flog n) and O(1) worst-case recourse.

A \(t\)-stretch tree cover of a metric space \(M = (X, \delta)\), for a parameter \(t \ge 1\), is a collection of trees such that every pair of points has a \(t\)-stretch path in one of the trees. Tree covers provide an important sketching tool that has found various applications over the years. The celebrated Dumbbell Theorem by Arya et al. [STOC’95] states that any set of points in the Euclidean plane admits a \((1+\epsilon)\)-stretch tree cover with \(O_\epsilon(1)\) trees. This result extends to any (constant) dimension and was also generalized for arbitrary doubling metrics by Bartal et al. [ICALP’19].

In their seminal paper, Althöfer et al. (DCG 1993) introduced the greedy spanner and showed that, for any weighted planar graph \(G\), the weight of the greedy \((1+\epsilon)\)-spanner is at most \((1+\tfrac{2}{\epsilon})\cdot \textrm w(\mathsf{MST}(G))\), where \(\textrm w(\mathsf{MST}(G))\) is the weight of a minimum spanning tree \(\mathrm{MST}(G)\) of \(G\). This bound is optimal in an \(\textcolor{#ff6666}{existential\ sense}\): there exist planar graphs \(G\) for which any \((1+\epsilon)\)-spanner has a weight of at least \((1+\tfrac{2}{\epsilon})\cdot w(\mathrm{MST}(G))\).

Vizing’s theorem states that any \(n\)-vertex \(m\)-edge graph of maximum degree \(\Delta\) can be edge colored using at most \(\Delta + 1\) different colors. Vizing’s original proof is easily translated into a deterministic \(O(mn)\) time algorithm. This deterministic time bound was subsequently improved to \(\tilde{O}(m\sqrt{n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem .

In their breakthrough ICALP’15 paper, Bernstein and Stein presented an algorithm for maintaining a \((3/2+\epsilon)\) -approximate maximum matching in fully dynamic bipartite graphs with a worst-case update time of \(O_{\epsilon}(m^{1/4})\) ; we use the \(O_{\epsilon}\) notation to suppress the \(\epsilon\) -dependence. Their main technical contribution was in presenting a new type of bounded-degree subgraph, which they named an edge degree constrained subgraph (EDCS) , which contains a large matching—of size that is smaller than the maximum matching size of the entire graph by at most a \(3/2+\epsilon\) factor. They demonstrate that the EDCS can be maintained with a worst-case update time of \(O_{\epsilon}(m^{1/4})\) , and their main result follows as a direct corollary. In their followup SODA’16 paper, Bernstein and Stein generalized their result for general graphs, achieving the same update time of \(O_{\epsilon}(m^{1/4})\) , albeit with an amortized rather than worst-case bound. To date, the best deterministic worst-case update time bound for any better-than-2 approximate matching is \(O(\sqrt{m})\) [Neiman and Solomon, STOC’13] and [Gupta and Peng, FOCS’13]; allowing randomization (against an oblivious adversary) one can achieve a much better (still polynomial) update time for approximation slightly below 2 [Behnezhad et al., SODA’20]. In this work we ( quasi nanos, gigantium humeris insidentes ) simplify the approach of Bernstein and Stein for bipartite graphs, which allows us to generalize it to general graphs while maintaining the same \(O_{\epsilon}(m^{1/4})\) bound on the worst-case update time. Moreover, our approach is density-sensitive : If the arboricity of the dynamic graph is always bounded by \(\alpha\) , then the worst-case update time of the algorithm is \(O_{\epsilon}(\sqrt{\alpha})\) .

Vizing’s Theorem from 1964 states that any n-vertex m-edge graph with maximum degree Δ can be edge colored using at most Δ + 1 colors. For over 40 years, the state-of-the-art running time for computing such a coloring, obtained independently by Arjomandi [1982] and by Gabow, Nishizeki, Kariv, Leven and Terada [1985], was . Very recently, this time bound was improved in two independent works, by Bhattacharya, Carmon, Costa, Solomon and Zhang to , and by Assadi to Õ (n2).

The dynamic set cover problem has been subject to extensive research since the pioneering works of [BHI, ICALP’15] and [GKKP17, STOC’17]. The input is a set system (U, S ) on a fixed collection S of sets and a dynamic universe of elements, where each element appears in a most f sets and the cost of each set lies in the range [1/C, 1]; the ultimate goal is to maintain a set cover under insertions and deletions of elements, with optimal bounds on both the approximation factor and the update time.

Vizing’s theorem states that any n-vertex m-edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to Õ(m√n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n2) by [Assadi, 2024] and Õ(mn1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn1/4) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ+1)-edge coloring in near-linear time—in fact, only O(mlogΔ) time—with high probability, giving a near-optimal algorithm for this fundamental problem.

Abstract. Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 1980s and early 1990s state that for any [Formula: see text]-dimensional [Formula: see text]-point Euclidean space, there exists a [Formula: see text]-spanner with [Formula: see text] edges and lightness (normalized weight) [Formula: see text]. Surprisingly, the fundamental question of whether or not these dependencies on [Formula: see text] and [Formula: see text] for small [Formula: see text] can be improved has remained elusive, even for [Formula: see text]. This question naturally arises in any application of Euclidean spanners where precision is a necessity (thus [Formula: see text] is tiny). In the most extreme case [Formula: see text] is inverse polynomial in [Formula: see text], and then one could potentially improve the size and lightness bounds by factors that are polynomial in [Formula: see text]. The state-of-the-art bounds [Formula: see text] and [Formula: see text] on the size and lightness of spanners are realized by the greedy spanner. In 2016, in a preliminary version, Filtser and Solomon [ SIAM J. Comput., 49 (2020), pp. 429–447] proved that, in low-dimensional spaces, the greedy spanner is “near-optimal”; informally, their result states that the greedy spanner for dimension [Formula: see text] is just as sparse and light as any other spanner but for dimension larger by a constant factor. Hence the question of whether the greedy spanner is truly optimal remained open to date. The contribution of this paper is twofold: (1) We resolve these longstanding questions by nailing down the dependencies on [Formula: see text] and [Formula: see text] and showing that the greedy spanner is truly optimal. Specifically, for any [Formula: see text], (a) we show that there are [Formula: see text]-point sets in [Formula: see text] for which any [Formula: see text]-spanner must have [Formula: see text] edges, implying that the greedy (and other) spanners achieve the optimal size; (b) we show that there are [Formula: see text]-point sets in [Formula: see text] for which any [Formula: see text]-spanner must have lightness [Formula: see text], and then improve the upper bound on the lightness of the greedy spanner from [Formula: see text] to [Formula: see text]. (The lightness upper and lower bounds match up to a lower-order term.) (2) We then complement our negative result for the size of spanners with a rather counterintuitive positive result: Steiner points lead to a quadratic improvement in the size of spanners! Our bound for the size of Steiner spanners in [Formula: see text] is tight as well (up to a lower-order term).

Abstract. We present a unified framework for constructing light spanners in a variety of graph classes. Informally, the framework boils down to a transformation from sparse spanners to light spanners; since the state-of-the-art for sparse spanners is much more advanced than that for light spanners, such a transformation is powerful. Our framework is developed in two papers. The current paper is the first of the two—it lays the basis of the unified framework and then applies it to design fast constructions with optimal lightness for several graph classes. Our new constructions are significantly faster than the state-of-the-art for every graph class studied in this paper; the running times of our constructions are near-linear and usually optimal. Among various applications and implications of our framework, we highlight here the following (for simplicity assume [Formula: see text] is fixed): (1) In low-dimensional Euclidean spaces, we present a construction of [Formula: see text]-spanners for [Formula: see text]-point sets with lightness and degree both bounded by constants, running in [Formula: see text] time in the algebraic computation tree (ACT) (or real-RAM) model, which is the basic model used in computational geometry. Our construction is optimal with respect to all the involved quality measures—running time, lightness, and degree—and it resolves a major problem in the area of geometric spanners, which was open for three decades. (2) In general graphs, we present a near-linear time algorithm for constructing light spanners of graphs with [Formula: see text] vertices and [Formula: see text] edges. Specifically, for any [Formula: see text], we construct a [Formula: see text]-spanner with lightness [Formula: see text] in [Formula: see text] time, where [Formula: see text] is the inverse Ackermann function; the lightness bound matches Erdős’ girth conjecture up to the [Formula: see text]-dependency. (Our companion paper builds on the basis laid in this paper, aiming to achieve optimality in a more refined sense, which takes into account a wider range of involved parameters, most notably [Formula: see text], but also others such as the Euclidean dimension or the minor size (in minor-free graphs).)

A $(1+\varepsilon)\textit{-stretch tree cover}$ of a metric space is a collection of trees, where every pair of points has a $(1+\varepsilon)$-stretch path in one of the trees. The celebrated $\textit{Dumbbell Theorem}$ [Arya et~al. STOC'95] states that any set of $n$ points in $d$-dimensional Euclidean space admits a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d} \cdot \log(1/\varepsilon))$ trees, where the $O_d$ notation suppresses terms that depend solely on the dimension~$d$. The running time of their construction is $O_d(n \log n \cdot \frac{\log(1/\varepsilon)}{\varepsilon^{d}} + n \cdot \varepsilon^{-2d})$. Since the same point may occur in multiple levels of the tree, the $\textit{maximum degree}$ of a point in the tree cover may be as large as $Ω(\log Φ)$, where $Φ$ is the aspect ratio of the input point set. In this work we present a $(1+\varepsilon)$-stretch tree cover with $O_d(\varepsilon^{-d+1} \cdot \log(1/\varepsilon))$ trees, which is optimal (up to the $\log(1/\varepsilon)$ factor). Moreover, the maximum degree of points in any tree is an $\textit{absolute constant}$ for any $d$. As a direct corollary, we obtain an optimal {routing scheme} in low-dimensional Euclidean spaces. We also present a $(1+\varepsilon)$-stretch $\textit{Steiner}$ tree cover (that may use Steiner points) with $O_d(\varepsilon^{(-d+1)/{2}} \cdot \log(1/\varepsilon))$ trees, which too is optimal. The running time of our two constructions is linear in the number of edges in the respective tree covers, ignoring an additive $O_d(n \log n)$ term; this improves over the running time underlying the Dumbbell Theorem.

Vizing's theorem asserts the existence of a $(Δ+1)$-edge coloring for any graph $G$, where $Δ= Δ(G)$ denotes the maximum degree of $G$. Several polynomial time $(Δ+1)$-edge coloring algorithms are known, and the state-of-the-art running time (up to polylogarithmic factors) is $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})$, by Gabow et al.\ from 1985, where $n$ and $m$ denote the number of vertices and edges in the graph, respectively. (The $\tilde{O}$ notation suppresses polylogarithmic factors.) Recently, Sinnamon shaved off a polylogarithmic factor from the time bound of Gabow et al. The {arboricity} $α= α(G)$ of a graph $G$ is the minimum number of edge-disjoint forests into which its edge set can be partitioned, and it is a measure of the graph's "uniform density". While $α\le Δ$ in any graph, many natural and real-world graphs exhibit a significant separation between $α$ and $Δ$. In this work we design a $(Δ+1)$-edge coloring algorithm with a running time of $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})\cdot \fracαΔ$, thus improving the longstanding time barrier by a factor of $\fracαΔ$. In particular, we achieve a near-linear runtime for bounded arboricity graphs (i.e., $α= \tilde{O}(1)$) as well as when $α= \tilde{O}(\fracΔ{\sqrt{n}})$. Our algorithm builds on Sinnamon's algorithm, and can be viewed as a density-sensitive refinement of it.

Euclidean spanners are important geometric objects that have been extensively studied since the 1980s. The two most basic “compactness” measures of a Euclidean spanner$E$12We shall identify a graph$H = (X,E)$with its edge set$E$. All edge weights are given by the Euclidean distances. are the size (number of edges)$\vert E\vert$and the weight (sum of edge weights)$\Vert E\Vert$. The state-of-the-art constructions of Euclidean$(1+\epsilon)$-spanners in$\mathbb{R}^{d}$have$o_{d}(_{n\cdot\epsilon^{-d+1}})$edges (or sparsity$O_{d}(\epsilon^{-d+1}))$and weight$O_{d}(\epsilon^{-d} \log \epsilon^{-1}) \cdot\Vert E_{\text{mst}}\Vert$(or lightness$O_{d}(\epsilon^{-d}\log\epsilon^{-1}))$; here$O_{d}$suppresses a factor of$d^{O(d)}$and$\Vert E_{\text{mst}}\Vert$denotes the weight of a minimum spanning tree of the input point set. Importantly, these two upper bounds are (near-)optimal (up to the$d^{O(d)}$factor and disregarding the factor of$\log(\epsilon^{-1})$in the lightness bound) for some extremal instances [Le and Solomon, 2019], and therefore they are (near-)optimal in an existential sense. Moreover, both these upper bounds are attained by the same construction-the classic greedy spanner, whose sparsity and lightness are not only existentially optimal, but they also significantly outperform those of any other Euclidean spanner construction studied in an experimental study by [Farshi-Gudmundsson, 2009] for various practical point sets in the plane. This raises the natural question of whether the greedy spanner is (near-) optimal for any point set instance? Motivated by this question, we initiate the study of instance optimal Euclidean spanners. Our results are two-fold. •Rather surprisingly (given the aforementioned experimental study), we demonstrate that the greedy spanner is far from being instance optimal, even when allowing its stretch to grow. More concretely, we design two hard instances of point sets in the plane, where the greedy$(1+x\epsilon)$-spanner (for basically any parameter$x \geq 1$) has$\Omega_{x}(\epsilon^{-1/2})\cdot\vert E_{\text{spa}} \vert$edges and weight$\Omega_{x}(\epsilon^{-1})\cdot\Vert E_{\text{light}}\Vert$, where$E_{\text{spa}}$and$E_{\text{light}}$denote the per-instance sparsest and lightest$(1 +\epsilon)$-spanners, respectively, and the$\Omega_{x}$notation suppresses a polynomial dependence on$1/x$. •As our main contribution, we design a new construction of Euclidean spanners, which is inherently different from known constructions, achieving the following bounds: a stretch of$1+\epsilon\cdot 2^{O(\log^{*}(d/\epsilon)}$with$O(1)\cdot\vert E_{\text{spa}}\vert$edges and weight$O(1)$. $\Vert E_{ \text{light}}\Vert$. In other words, we show that a slight increase to the stretch suffices for obtaining instance optimality up to an absolute constant for both sparsity and lightness. Remarkably, there is only a log-star dependence on the dimension in the stretch, and there is no dependence on it whatsoever in the number of edges and weight. In general, for any integer$k\geq 1$, we can construct a Euclidean spanner in$\mathbb{R}^{d}$of stretch$1+\epsilon\cdot 2^{O(k)}$with$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\vert E_{\text{spa}}\vert$edges and weight$O(\log^{(k)}(\epsilon^{-1})+\log^{(k-1)}(d))\cdot\Vert E_{\text{light}}\Vert$, where$\log^{(k)}$denotes the k-iterated logarithm.

Vizing's theorem states that any n-vertex m-edge graph of maximum degree$\Delta$can be edge colored using at most$\Delta+1$different colors [Diskret. Analiz, '64]. Vizing's original proof is algorithmic and shows that such an edge coloring can be found in$\tilde{O}(mn)$time. This was subsequently improved to$\tilde{O}(m\sqrt{n})$, independently by Arjomandi [1982] and by Gabow et al. [1985]. In this paper we present an algorithm that computes such an edge coloring in$\tilde{O}(mn^{1/3})$, time, giving the first polynomial improvement for this fundamental problem in over 40 years.

The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most$n$elements and a fixed collection of$m$sets, where each element appears in a most$f$sets and the cost of each set is in [1/C, 1], and the goal is to efficiently maintain an approximate minimum set cover under element updates. Two algorithms that dynamize the classic greedy algorithm are known, providing$O(\log n)$and$((1+\epsilon)\ln n)$-approximation with amortized update times$O(f \log n)$and,$O(\frac{f \log n}{\epsilon})$, respectively [GKKP (STOC'17); SU (STOC'23)]. The question of whether one can get approximation$O(\log n)$(or even worse) with low worst-case update time has remained open — only the naive$O(f\cdot n)$time bound is known, even for unweighted instances. In this work we devise the first amortized greedy algorithm that is amenable to an efficient deamortization, and also develop a lossless deamortization approach suitable for the set cover problem, the combination of which yields a$((1+\epsilon)\ln n){-}$approximation algorithm with a worst-case update time of$O(\frac{f \log n}{\epsilon^{2}})$. Our worst-case time bound — the first to break the naive$O(f\cdot n)$bound — matches the previous best amortized bound, and actually improves its$\epsilon$-dependence. Further, to demonstrate the applicability of our deamortization approach, we employ it, in conjunction with the primal-dual amortized algorithm of [BHN (FOCS'19)], to obtain a$((1+\epsilon)f)$-approximation algorithm with a worst-case update time of$O(\frac{f \log n}{\epsilon^{2}})$, improving over the previous best bound of$O(\frac{f \cdot \log ^{2}(C n)}{-3})\ [$BHNW (SODA'21)]. Finally, as direct implications of our results for set cover, we (i) achieve the first nontrivial worst-case update time for the dominating set problem, and (ii) improve the state-of-the-art worst-case update time for the vertex cover problem.

We consider the problem of maintaining a (1 + ɛ)∆-edge coloring in a dynamic graph G with n nodes and maximum degree at most Δ. The state-of-the-art update time is Oɛ(polylog(n)), by Duan, He and Zhang [SODA’19] and by Christiansen [STOC’23], and more precisely O(log7 n/ɛ2), where Δ = Ω(log2 n/ɛ2).

The notion of shortcut partition, introduced recently by Chang, Conroy, Le, Milenković, Solomon, and Than [CCL+23], is a new type of graph partition into low-diameter clusters. Roughly speaking, the shortcut partition guarantees that for every two vertices u and v in the graph, there exists a path between u and v that intersects only a few clusters. They proved that any planar graph admits a shortcut partition and gave several applications, including a construction of tree cover for arbitrary planar graphs with stretch 1 + ɛ and O(1) many trees for any fixed ɛ ∈ (0,1). However, the construction heavily exploits planarity in multiple steps, and is thus inherently limited to planar graphs.

While research on the geometry of planar graphs has been active in the past decades, many properties of planar metrics remain mysterious. This paper studies a fundamental aspect of the planar graph geometry: covering planar metrics by a small collection of simpler metrics. Specifically, a tree cover of a metric space $(X, \delta)$ is a collection of trees, so that every pair of points u and v in X has a low-distortion path in at least one of the trees.The celebrated “Dumbbell Theorem” [ADM+95] states that any low-dimensional Euclidean space admits a tree cover with $O(1)$ trees and distortion $1+\varepsilon$, for any fixed $\varepsilon \in(0,1)$. This result has found numerous algorithmic applications, and has been generalized to the wider family of doubling metrics [BFN19]. Does the same result hold for planar metrics? A positive answer would add another evidence to the well-observed connection between Euclidean/doubling metrics and planar metrics.In this work, we answer this fundamental question affirmatively. Specifically, we show that for any given fixed $\varepsilon \in(0,1)$, any planar metric can be covered by $O(1)$ trees with distortion $1+\varepsilon$. Our result for planar metrics follows from a rather general framework: First we reduce the problem to constructing tree covers with additive distortion. Then we introduce the notion of shortcut partition, and draw connection between shortcut partition and additive tree cover. Finally we prove the existence of shortcut partition for any planar metric, using new insights regarding the grid-like structure of planar graphs. To demonstrate the power of our framework:•We establish additional tree cover results beyond planar metrics; in particular, we present an $O(1)$-size tree cover with distortion $1+\varepsilon$ for bounded treewidth metrics;•We obtain several algorithmic applications in planar graphs from our tree cover. The grid-like structure is a technical contribution that we believe is of independent interest. We showcase its applicability beyond tree cover by constructing a simpler and better embedding of planar graphs into $O(1)$-treewidth graphs with small additive distortion, resolving an open problem in this line of research.

An essential requirement of spanners in many applications is to be fault-tolerant: a $(1+\epsilon)$-spanner of a metric space is called (vertex) f-fault-tolerant $(f-F T)$ if it remains a $(1+\epsilon)$-spanner (for the non-faulty points) when up to f faulty points are removed from the spanner. Fault-tolerant (FT) spanners for Euclidean and doubling metrics have been extensively studied since the 90 s. For low-dimensional Euclidean metrics, Czumaj and Zhao in SoCG’03 [CZ03] showed that the optimal guarantees $O(f n), O(f)$ and $O\left(f^{2}\right)$ on the size, degree and lightness of f-FT spanners can be achieved via a greedy algorithm, which naïvely runs in $O\left(n^{3}\right) \cdot 2^{O(f)}$ time.$^{1}$ An earlier construction, by Levcopoulos et al. [LNS98] from STOC’98, has a faster running time of $O(n \log n)+n 2^{O(f)}$, but has a slack of $2^{\Omega(f)}$ in all the three involved parameters. The question of whether the optimal bounds of [CZ03] can be achieved via a fast construction has remained elusive, with the lightness parameter being the bottleneck: Any construction (other than [CZ03]) has lightness either $2^{\Omega(f)}$ or $\Omega(\log n)$. Moreover, in the wider family of doubling metrics, it is not even clear whether there exists an f FT spanner with lightness that depends solely on f (even exponentially): all existing constructions have lightness $\Omega(\log n)$ since they are built on the net-tree spanner, which is induced by a hierarchical net-tree of lightness $\Omega(\log n)$. In this paper we settle in the affirmative these longstanding open questions. Specifically, we design a construction of f-FT spanners that is optimal with respect to all the involved parameters (size, degree, lightness and running time): For any n-point doubling metric, any $\epsilon\gt0$, and any integer $1 \le \log f n\le + {nfn}-)$, an2, our construction provides,-spanner with within time $O(n$ size $O (fn)$, degree $O(f)$ and lightness $O(f^{2})$. To break the $\Omega (\log n)$ lightness barrier, we introduce a new geometric object — the light net-forest. Like the net-tree, the light net-forest is induced by a hierarchy of nets. However, to ensure small lightness, the light net-forest is inherently less “well-connected” than the net-tree, which, in turn, makes the task of achieving fault-tolerance significantly more challenging. Further, to achieve the optimal degree (and size) together with optimal lightness, and to do so within the optimal running time — we overcome several highly nontrivial technical challenges.

Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Three shortcomings of previous works on light spanners are: (i) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. (ii) These constructions are optimal in the standard and crude sense, but not in a refined sense that takes into account a wider range of involved parameters. (iii) The techniques are ad hoc per graph class, and thus can’t be applied broadly.

The minimum set cover (MSC) problem admits two classic algorithms: a greedy lnn-approximation and a primal-dual f-approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably — one cannot improve these approximations under hardness results by more than a factor of (1+є), for any constant є > 0.

In STOC'95 [ADMSS95] Arya et al. showed that any set of n points in R^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter at most k and O(n α_k(n)) edges, for any k≥2. The function α_k is the inverse of a certain Ackermann-style function at the ⌊k/2⌋th level of the primitive recursive hierarchy, where α₀(n)=⌈n/2⌉, α₁(n)=⌈√n⌉, α₂(n)=⌈log n⌉, α₃(n)=⌈log log n⌉, α₄(n)=log^* n, α₅(n)=⌊1/2 log^*n⌋, .... Roughly speaking, for k≥2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars. Also, α_{2α(n)+4}(n)≤4, where α(n) is the one-parameter inverse Ackermann function, which is an extremely slowly growing function. Whether or not this tradeoff is tight has remained open, even for the cases k=2 and k=3. Two lower bounds are known: The first applies only to spanners with stretch 1 and the second is sub-optimal and applies only to sufficiently large (constant) values of k. In this paper we prove a tight lower bound for any constant k: For any fixed ε>0, any (1+ε)-spanner for the uniform line metric with hop-diameter at most k must have at least Ω(n α_k(n)) edges.

The field of dynamic graph algorithms aims at achieving a thorough understanding of real-world networks whose topology evolves with time. Traditionally, the focus has been on the classic sequential, centralized setting where the main quality measure of an algorithm is its update time, i.e. the time needed to restore the solution after each update. While real-life networks are very often distributed across multiple machines, the fundamental question of finding efficient dynamic, distributed graph algorithms received little attention to date. The goal in this setting is to optimize both the round and message complexities incurred per update step, ideally achieving a message complexity that matches the centralized update time in $O(1)$ (perhaps amortized) rounds. Toward initiating a systematic study of dynamic, distributed algorithms, we study some of the most central symmetry-breaking problems: maximal independent set (MIS), maximal matching/(approx-) maximum cardinality matching (MM/MCM), and $(Δ+ 1)$-vertex coloring. This paper focuses on dynamic, distributed algorithms that are deterministic, and in particular -- robust against an adaptive adversary. Most of our focus is on our MIS algorithm, which achieves $O\left(m^{2/3}\log^2 n\right)$ amortized messages in $O\left(\log^2 n\right)$ amortized rounds in the Congest model. Notably, the amortized message complexity of our algorithm matches the amortized update time of the best-known deterministic centralized MIS algorithm by Gupta and Khan [SOSA'21] up to a polylog $n$ factor. The previous best deterministic distributed MIS algorithm, by Assadi et al. [STOC'18], uses $O(m^{3/4})$ amortized messages in $O(1)$ amortized rounds, i.e., we achieve a polynomial improvement in the message complexity by a polylog $n$ increase to the round complexity; moreover, the algorithm of Assadi et al. makes an implicit assumption that the [...]

Spanners for metric spaces have been extensively studied, perhaps most notably in low-dimensional Euclidean spaces - due to their numerous applications. Euclidean spanners can be viewed as means of compressing the (n2) pairwise distances of a d-dimensional Euclidean space into O(n) = O∈,d (n) spanner edges, so that the spanner distances preserve the original distances to within a factor of 1 + ε, for any ε > 0. Moreover, one can compute such spanners efficiently in the standard centralized and distributed settings. Once the spanner has been computed, it serves as a "proxy" overlay network, on which the computation can proceed, which gives rise to huge savings in space and other important quality measures. The original metric enables us to "navigate" optimally - a single

Let G = (V, E, w) be a weighted undirected graph on |V| = n vertices and |E| = m edges, let k ≥ 1 be any integer, and let ∊ < 1 be any parameter. We present the following results on fast constructions of spanners with near-optimal sparsity and lightness,1 which culminate a long line of work in this area. (By near-optimal we mean optimal under Erdos' girth conjecture and disregarding the ∊-dependencies.) There are (deterministic) algorithms for constructing (2k–1)(1 + ∊)-spanners for G with a near-optimal sparsity of O(n1/k · log(1/∊)/∊)). The first algorithm can be implemented in the pointer-machine model within time O(mα(m, n) · log(1/∊)/∊)+ SORT(m)), where α(·,·) is the two-parameter inverse-Ackermann function and SORT(m) is the time needed to sort m integers. The second algorithm can be implemented in the Word RAM model within time O(m log(1/∊)/∊)). There is a (deterministic) algorithm for constructing a (2k–1)(1 + ∊)-spanner for G that achieves a near-optimal bound of O(n1/k ·poly(1/∊)) on both sparsity and lightness. This algorithm can be implemented in the pointer-machine model within time O(mα(m,n) · poly(1/∊) + SORT(m)) and in the Word RAM model within time O(mα(m,n) · poly(1/∊)). The previous fastest constructions of (2k–1)(1 + ∊)-spanners with near-optimal sparsity incur a runtime of is O(min{m(n1+1/k) + n log n, k · n2+1/k}), even regardless of the lightness. Importantly, the greedy spanner for stretch 2k–1 has sparsity O(n1/k) — with no ∊-dependence whatsoever, but its runtime is O(m(n1+1/k + n log n)). Moreover, the state-of-the-art lightness bound of any (2k–1)-spanner (including the greedy spanner) is poor, even regardless of the sparsity and runtime.

The problem of (Δ +1)-vertex coloring a graph of maximum degree Δ has been extremely well studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA’18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized algorithm for maintaining a (Δ +1)-coloring with O (log Δ) expected amortized update time. In this article, we present an improved randomized algorithm for (Δ +1)-coloring that achieves O (1) amortized update time and show that this bound holds not only in expectation but also with high probability. Our starting point is the state-of-the-art randomized algorithm for maintaining a maximal matching (Solomon, FOCS’16). We carefully build on the approach of Solomon, but, due to inherent differences between the maximal matching and (Δ +1)-coloring problems, we need to deviate significantly from it in several crucial and highly nontrivial points. 1

The goal in reconfiguration problems is to compute a gradual transformation between two feasible solutions of a problem such that all intermediate solutions are also feasible. In the Matching Reconfiguration Problem (MRP), proposed in a pioneering work by Ito et al. from 2008, we are given a graph G and two matchings M and M', and we are asked whether there is a sequence of matchings in G starting with M and ending at M', each resulting from the previous one by either adding or deleting a single edge in G, without ever going through a matching of size < min{|M|,|M'|}-1. Ito et al. gave a polynomial time algorithm for the problem, which uses the Edmonds-Gallai decomposition. In this paper we introduce a natural generalization of the MRP that depends on an integer parameter Δ ≥ 1: here we are allowed to make Δ changes to the current solution rather than 1 at each step of the {transformation procedure}. There is always a valid sequence of matchings transforming M to M' if Δ is sufficiently large, and naturally we would like to minimize Δ. We first devise an optimal transformation procedure for unweighted matching with Δ = 3, and then extend it to weighted matchings to achieve asymptotically optimal guarantees. The running time of these procedures is linear. We further demonstrate the applicability of this generalized problem to dynamic graph matchings. In this area, the number of changes to the maintained matching per update step (the recourse bound) is an important quality measure. Nevertheless, the worst-case recourse bounds of almost all known dynamic matching algorithms are prohibitively large, much larger than the corresponding update times. We fill in this gap via a surprisingly simple black-box reduction: Any dynamic algorithm for maintaining a β-approximate maximum cardinality matching with update time T, for any β ≥ 1, T and ε > 0, can be transformed into an algorithm for maintaining a (β(1 +ε))-approximate maximum cardinality matching with update time T + O(1/ε) and worst-case recourse bound O(1/ε). This result generalizes for approximate maximum weight matching, where the update time and worst-case recourse bound grow from T + O(1/ε) and O(1/ε) to T + O(ψ/ε) and O(ψ/ε), respectively; ψ is the graph aspect-ratio. We complement this positive result by showing that, for β = 1+ε, the worst-case recourse bound of any algorithm produced by our reduction is optimal. As a corollary, several key dynamic approximate matching algorithms - with poor worst-case recourse bounds - are strengthened to achieve near-optimal worst-case recourse bounds with no loss in update time.

We revisit the minimum dominating set problem on graphs with arboricity bounded by α. In the (standard) centralized setting, Bansal and Umboh [Bansal and Umboh, 2017] gave an O(α)-approximation LP rounding algorithm, which also translates into a near-linear time algorithm using general-purpose approximation results for explicit mixed packing and covering or pure covering LPs [Koufogiannakis and Young, 2014; Young, 2014; Allen-Zhu and Orecchia, 2019; Quanrud, 2020]. Moreover, [Bansal and Umboh, 2017] showed that it is NP-hard to achieve an asymptotic improvement for the approximation factor. On the other hand, the previous two non-LP-based algorithms, by Lenzen and Wattenhofer [Christoph Lenzen and Roger Wattenhofer, 2010], and Jones et al. [Jones et al., 2013], achieve an approximation factor of O(α²) in linear time. There is a similar situation in the distributed setting: While there is an O(log² n)-round LP-based O(α)-approximation algorithm implied in [Kuhn et al., 2006], the best non-LP-based algorithm by Lenzen and Wattenhofer [Christoph Lenzen and Roger Wattenhofer, 2010] is an implementation of their centralized algorithm, providing an O(α²)-approximation within O(log n) rounds. We address the questions of whether one can achieve an O(α)-approximation algorithm that is elementary, i.e., not based on any LP-based methods, either in the centralized setting or in the distributed setting. We resolve both questions in the affirmative, and en route achieve algorithms that are faster than the state-of-the-art LP-based algorithms. Our contribution is two-fold: 1) In the centralized setting, we provide a surprisingly simple combinatorial algorithm that is asymptotically optimal in terms of both approximation factor and running time: an O(α)-approximation in linear time. The previous state-of-the-art O(α)-approximation algorithms are (1) LP-based, (2) more complicated, and (3) have super-linear running time. 2) Based on our centralized algorithm, we design a distributed combinatorial O(α)-approximation algorithm in the CONGEST model that runs in O(αlog n) rounds with high probability. Not only does this result provide the first nontrivial non-LP-based distributed o(α²)-approximation algorithm for this problem, it also outperforms the best LP-based distributed algorithm for a wide range of parameters.

The FOCS'19 paper of Le and Solomon [Hung Le and Shay Solomon, 2019], culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy (1+ε)-spanner in ℝ^d is Õ(ε^{-d}) for any d = O(1) and any ε = Ω(n^{-1/(d-1)}) (where Õ hides polylogarithmic factors of 1/ε), and also shows the existence of point sets in ℝ^d for which any (1+ε)-spanner must have lightness Ω(ε^{-d}). Given this tight bound on the lightness, a natural arising question is whether a better lightness bound can be achieved using Steiner points. Our first result is a construction of Steiner spanners in ℝ² with lightness O(ε^{-1} log Δ), where Δ is the spread of the point set. In the regime of Δ ≪ 2^(1/ε), this provides an improvement over the lightness bound of [Hung Le and Shay Solomon, 2019]; this regime of parameters is of practical interest, as point sets arising in real-life applications (e.g., for various random distributions) have polynomially bounded spread, while in spanner applications ε often controls the precision, and it sometimes needs to be much smaller than O(1/log n). Moreover, for spread polynomially bounded in 1/ε, this upper bound provides a quadratic improvement over the non-Steiner bound of [Hung Le and Shay Solomon, 2019], We then demonstrate that such a light spanner can be constructed in O_ε(n) time for polynomially bounded spread, where O_ε hides a factor of poly(1/(ε)). Finally, we extend the construction to higher dimensions, proving a lightness upper bound of Õ(ε^{-(d+1)/2} + ε^{-2} log Δ) for any 3 ≤ d = O(1) and any ε = Ω(n^{-1/(d-1)}).

The neighborhood independence number of a graph G, denoted by β = β(G), is the size of the largest independent set in the neighborhood of any vertex. Graphs with bounded neighborhood independence, already for constant β, constitute a wide family of possibly dense graphs, including line graphs, unit-disk graphs, claw-free graphs and graphs of bounded growth, which has been well-studied in the area of distributed computing. In ICALP'19, Assadi and Solomon [8] showed that, for any n-vertex graph G, a maximal matching can be computed in O(n log n · β) time in the classic sequential setting. This result shows that, surprisingly, for almost the entire regime of parameter β, a maximal matching can be computed much faster than reading the entire input. The algorithm of [8], however, is inherently sequential and centralized. Moreover, a maximal matching provides a 2-approximate (maximum) matching, and the question of whether a better-than-2-approximate matching can be computed in sublinear time remained open.

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 existentially optimal (or existentially near-optimal) for several important graph families in terms of both size and weight. Roughly speaking, the greedy spanner is said to be existentially optimal (or near-optimal) for a graph family $\mathcal G$ if the worst performance of the greedy spanner over all graphs in $\mathcal G$ is just as good (or nearly as good) as the worst performance of an optimal spanner over all graphs in $\mathcal G$. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs (due to Chechik and Wulff-Nilsen [ ACM Trans. Algorithms, 14 (2018), 33]) and doubling metrics (due to Gottlieb [ Proceedings of the $56$th Annual IEEE Symposium on Foundations of Computer Science, 2015, pp. 759--772]) are complex. Plugging our observation into 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 spanners are existentially near-optimal as well. Consequently, we provide an $O(n \log n)$-time construction of $(1+\epsilon)$-spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is $O(n \log^2 n)$ and whose number of edges and degree are unbounded, and, remarkably, it matches the state-of-the-art Euclidean result (due to Gudmundsson, Levcopoulos, and Narasimhan [ SIAM J. Comput., 31 (2002), pp. 1479--1500]) in all of the involved parameters (up to dependencies on $\epsilon$ and the dimension).

We consider the problem of maintaining a maximal independent set in a dynamic graph subject to edge insertions and deletions. Recently, Assadi et al. (at STOC’18) showed that a maximal independent set can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this article, we significantly improve the update time for uniformly sparse graphs . Specifically, for graphs with arboricity α, the amortized update time of our algorithm is O (α 2 ⋅ log 2 n ), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs and some classes of “real-world” graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m 3/8−ϵ , for any constant ϵ > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m 1/2 .

This article studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n1-εfor any ε > 0, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring or alternatively, study restricted families of graphs. Toward understanding the combinatorial aspects of this problem, one may assume a black-box access to a static algorithm forC-coloring any subgraph of the dynamic graph, and investigate the trade-off between the number of colors and the number of recolorings per update step. Optimizing the number of recolorings, sometimes referred to as the recourse bound, is important for various practical applications. In WADS ’17, Barba et al. devised two complementary algorithms: for any β > 0, the first (respectively, second) maintains anO(Cβn1/β)(respectively,O(Cβ)-coloring while recoloring O(β) (respectively, O(βn1/β)) vertices per update. Barba et al. also showed that the second trade-off appears to exhibit the right behavior, at least for β = O(1): any algorithm that maintains aC-coloring of ann-vertex dynamic forest must recolor Ω (n2C(C-1)) vertices per update, for any constant C ≥ 2. Our contribution is twofold: • We devise a new algorithm for general graphs that improves significantly upon the first trade-off in a wide range of parameters: for any β > 0, we get a Ô (Cβlog2n)-coloring with O(β) recolorings per update, where the Ô notation suppressespolyloglog(n)factors. In particular, for β = O(1), we get constant recolorings withpolylog(n)colors; not only is this an exponential improvement over the previous bound but also it unveils a rather surprising phenomenon: the trade-off between the number of colors and recolorings is highly non-symmetric. • For uniformly sparse graphs, we use low out-degree orientations to strengthen the preceding result by bounding the update time of the algorithm rather than the number of recolorings. Then, we further improve this result by introducing a new data structure that refines bounded out-degree edge orientations and is of independent interest. From this data structure, we get a deterministic algorithm for graphs of arboricity ɑ that maintains an O(ɑ log2n)-coloring in amortized O(1) time.

Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 80s and early 90s state that for any d-dimensional n-point Euclidean space, there exists a (1+ε) -spanner with O(nε^-d+1) edges and lightness (normalized weight) O(ε^-2d)^1. Surprisingly, the fundamental question of whether or not these dependencies on ε and d for small d can be improved has remained elusive, even for d = 2. This question naturally arises in any application of Euclidean spanners where precision is a necessity (thus ε is tiny). In the most extreme case ε is inverse polynomial in n, and then one could potentially improve the size and lightness bounds by factors that are polynomial in n. The state-of-the-art bounds O(nε^-d+1) and O(ε^-2d) on the size and lightness of spanners are realized by the greedy spanner. In 2016, Filtser and Solomon [25] proved that, in low dimensional spaces, the greedy spanner is “near-optimal''; informally, their result states that the greedy spanner for dimension d is just as sparse and light as any other spanner but for dimension larger by a constant factor. Hence the question of whether the greedy spanner is truly optimal remained open to date. The contribution of this paper is two-fold. 1) We resolve these longstanding questions by nailing down the exact dependencies on ε and d and showing that the greedy spanner is truly optimal. Specifically, for any d= O(1), ε = Ω(n^-1/d-1): • We show that any (1+ε) -spanner must have Ω(nε^-d+1) edges, implying that the greedy (and other) spanners achieve the optimal size. • We show that any (1+ε) -spanner must have lightness Ω(ε^-d), and then improve the upper bound on the lightness of the greedy spanner from O(ε^-2d) to Õ_ε (ε^-d). 2) We then complement our negative result for the size of spanners with a rather counterintuitive positive result: Steiner points lead to a quadratic improvement in the size of spanners! Our bound for the size of Steiner spanners is tight as well (up to lower-order terms).

Maximal independent set (MIS), maximal matching (MM), and (Delta+1)-(vertex) coloring in graphs of maximum degree Delta are among the most prominent algorithmic graph theory problems. They are all solvable by a simple linear-time greedy algorithm and up until very recently this constituted the state-of-the-art. In SODA 2019, Assadi, Chen, and Khanna gave a randomized algorithm for (Delta+1)-coloring that runs in O~(n sqrt{n}) time, which even for moderately dense graphs is sublinear in the input size. The work of Assadi et al. however contained a spoiler for MIS and MM: neither problems provably admits a sublinear-time algorithm in general graphs. In this work, we dig deeper into the possibility of achieving sublinear-time algorithms for MIS and MM. The neighborhood independence number of a graph G, denoted by beta(G), is the size of the largest independent set in the neighborhood of any vertex. We identify beta(G) as the "right" parameter to measure the runtime of MIS and MM algorithms: Although graphs of bounded neighborhood independence may be very dense (clique is one example), we prove that carefully chosen variants of greedy algorithms for MIS and MM run in O(n beta(G)) and O(n log{n} * beta(G)) time respectively on any n-vertex graph G. We complement this positive result by observing that a simple extension of the lower bound of Assadi et al. implies that Omega(n beta(G)) time is also necessary for any algorithm to either problem for all values of beta(G) from 1 to Theta(n). We note that our algorithm for MIS is deterministic while for MM we use randomization which we prove is unavoidable: any deterministic algorithm for MM requires Omega(n^2) time even for beta(G) = 2. Graphs with bounded neighborhood independence, already for constant beta = beta(G), constitute a rich family of possibly dense graphs, including line graphs, proper interval graphs, unit-disk graphs, claw-free graphs, and graphs of bounded growth. Our results suggest that even though MIS and MM do not admit sublinear-time algorithms in general graphs, one can still solve both problems in sublinear time for a wide range of beta(G) << n. Finally, by observing that the lower bound of Omega(n sqrt{n}) time for (Delta+1)-coloring due to Assadi et al. applies to graphs of (small) constant neighborhood independence, we unveil an intriguing separation between the time complexity of MIS and MM, and that of (Delta+1)-coloring: while the time complexity of MIS and MM is strictly higher than that of (Delta+1) coloring in general graphs, the exact opposite relation holds for graphs with small neighborhood independence.

We study the matching problem in the incremental setting, where we are given a sequence of edge insertions and aim at maintaining a near-maximum cardinality matching of the graph with small update time. We present a deterministic algorithm that, for any constant ε > 0, maintains a (1 + ε)-approximate matching with constant amortized update time per insertion.

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et al., STOC’18]. The algorithm is deterministic and its update time is O(m3/4), where m is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of O(m2/3) and O(m2/3 ), respectively. Du and Zhang also gave a randomized algorithm with update time . Moreover, they provided some partial (conditional) hardness results hinting that the update time of m1/2–ε, and in particular n1–ε for n-vertex dense graphs, is a natural barrier for this problem for any constant ε > 0, for deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an expected amortized update. We also show that a simpler variant of our algorithm can already achieve an Õ(m1/3) expected amortized update time, which results in an improved performance over our update time algorithm for sufficiently sparse graphs, and breaks the m1/2 barrier of Du and Zhang for all values of m.

This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within n^{1-epsilon} for any epsilon > 0, is NP-hard in static graphs, there is no hope to achieve any meaningful computational results for general graphs in the dynamic setting. It is therefore only natural to consider the combinatorial aspects of dynamic coloring, or alternatively, study restricted families of graphs. Towards understanding the combinatorial aspects of this problem, one may assume a black-box access to a static algorithm for C-coloring any subgraph of the dynamic graph, and investigate the trade-off between the number of colors and the number of recolorings per update step. Optimizing the number of recolorings, sometimes referred to as the recourse bound, is important for various practical applications. In WADS'17, Barba et al. devised two complementary algorithms: For any beta > 0, the first (respectively, second) maintains an O(C beta n^{1/beta}) (resp., O(C beta))-coloring while recoloring O(beta) (resp., O(beta n^{1/beta})) vertices per update. Barba et al. also showed that the second trade-off appears to exhibit the right behavior, at least for beta = O(1): Any algorithm that maintains a c-coloring of an n-vertex dynamic forest must recolor Omega(n^{2/(c(c-1))}) vertices per update, for any constant c >= 2. Our contribution is two-fold: - We devise a new algorithm for general graphs that improves significantly upon the first trade-off in a wide range of parameters: For any beta > 0, we get a O~(C/(beta)log^2 n)-coloring with O(beta) recolorings per update, where the O~ notation supresses polyloglog(n) factors. In particular, for beta = O(1) we get constant recolorings with polylog(n) colors; not only is this an exponential improvement over the previous bound, but it also unveils a rather surprising phenomenon: The trade-off between the number of colors and recolorings is highly non-symmetric. - For uniformly sparse graphs, we use low out-degree orientations to strengthen the above result by bounding the update time of the algorithm rather than the number of recolorings. Then, we further improve this result by introducing a new data structure that refines bounded out-degree edge orientations and is of independent interest.

Despite significant research efforts, the state-of-the-art algorithm for maintaining an approximate matching in fully dynamic graphs has a polynomial {worst-case} update time, even for very poor approximation guarantees. In a recent breakthrough, Bhattacharya, Henzinger and Nanongkai showed how to maintain a constant approximation to the minimum vertex cover, and thus also a constant-factor estimate of the maximum matching size, with polylogarithmic worst-case update time. Later (in SODA'17 Proc.) they improved the approximation factor all the way to $2+ε$. Nevertheless, the longstanding fundamental problem of {maintaining} an approximate matching with sub-polynomial worst-case time bounds remained open. We present a randomized algorithm for maintaining an {almost-maximal} matching in fully dynamic graphs with polylogarithmic worst-case update time. Such a matching provides $(2+ε)$-approximations for both the maximum matching and the minimum vertex cover, for any $ε> 0$. Our result was done independently of the $(2+ε)$-approximation result of Bhattacharya et al., so it provides the first $(2+ε)$-approximation for minimum vertex cover (together with Bhattacharya et al.'s result) and the first $(2+ε)$-approximation for maximum (integral) matching. The polylogarithmic worst-case update time of our algorithm holds deterministically, while the almost-maximality guarantee holds with high probability. This result not only settles the aforementioned problem on dynamic matchings, but also provides essentially the best possible approximation guarantee for dynamic vertex cover (assuming the unique games conjecture).

We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (STOC 2018) showed that an MIS can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this paper we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity alpha, the amortized update time of our algorithm is O(alpha^2 * log^2 n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs as well as some classes of "real world" graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m^{3/8 - epsilon}, for any constant epsilon > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m^{1/2}.

In graph sparsification, the goal has almost always been of global nature: compress a graph into a smaller subgraph (sparsifier) that maintains certain features of the original graph. Algorithms can then run on the sparsifier, which in many cases leads to improvements in the overall runtime and memory. This paper studies sparsifiers that have bounded (maximum) degree, and are thus locally sparse, aiming to improve local measures of runtime and memory. To improve those local measures, it is important to be able to compute such sparsifiers locally. We initiate the study of local algorithms for bounded degree sparsifiers in unweighted sparse graphs, focusing on the problems of vertex cover, matching, and independent set. Let \eps > 0 be a slack parameter and \alpha \ge 1 be a density parameter. We devise local algorithms for computing: 1. A (1+\eps)-vertex cover sparsifier of degree O(\alpha / \eps), for any graph of arboricity \alpha.\footnote{In a graph of arboricity \alpha the average degree of any induced subgraph is at most 2\alpha.} 2. A (1+\eps)-maximum matching sparsifier and also a (1+\eps)-maximal matching sparsifier of degree O(\alpha / \eps, for any graph of arboricity \alpha. 3. A (1+\eps)-independent set sparsifier of degree O(\alpha^2 / \eps), for any graph of average degree \alpha. Our algorithms require only a single communication round in the standard message passing model of distributed computing, and moreover, they can be simulated locally in a trivial way. As an immediate application we can extend results from distributed computing and local computation algorithms that apply to graphs of degree bounded by d to graphs of arboricity O(d / \eps) or average degree O(d^2 / \eps), at the expense of increasing the approximation guarantee by a factor of (1+\eps). In particular, we can extend the plethora of recent local computation algorithms for approximate maximum and maximal matching from bounded degree graphs to bounded arboricity graphs with a negligible loss in the approximation guarantee. The inherently local behavior of our algorithms can be used to amplify the approximation guarantee of any sparsifier in time roughly linear in its size, which has immediate applications in the area of dynamic graph algorithms. In particular, the state-of-the-art algorithm for maintaining (2-\eps)-vertex cover (VC) is at least linear in the graph size, even in dynamic forests. We provide a reduction from the dynamic to the static case, showing that if a t-VC can be computed from scratch in time T(n) in any (sub)family of graphs with arboricity bounded by \alpha, for an arbitrary t \ge 1, then a (t+\eps)-VC can be maintained with update time \frac{T(n)}{O((n / \alpha) \cdot \eps^2)}, for any \eps > 0. For planar graphs this yields an algorithm for maintaining a (1+\eps)-VC with constant update time for any constant \eps > 0.

This paper introduces an extended notion of expansion suitable for radio networks. A graph G=(V,E) is said to be an (α_w, β_w) -\em wireless expander if for every subset S \subseteq V s.t. |S|łeq α_w \cdot |V| , there exists a subset S'\subseteq S s.t. there are at least β_w \cdot |S| vertices in V\backslash S that are adjacent in G to exactly one vertex in S' . The main question we ask is the following: to what extent are ordinary expanders also good wireless expanders? We answer this question in a nearly tight manner. On the positive side, we show that any (α, β)-expander with maximum degree Δ and β\geq 1/Δ$ is also a $(α_w, β_w)$ wireless expander with α_w \ge α$ and β_w = Ømega(β / łog (2 \cdot \min\Δ / β, Δ \cdot β\ ))$. Thus the wireless expansion can be smaller than the ordinary expansion by at most a factor that is logarithmic in \min\Δ / β, Δ \cdot β\ , which, in turn, depends on the average degree rather than the maximum degree of the graph. In particular, for low arboricity graphs (such as planar graphs), the wireless expansion matches the ordinary expansion up to a constant factor. We complement this positive result by presenting an explicit construction of a "bad'' (α, β) -expander for which the wireless expansion is β_w = O(β / łog (2 \cdot \min\Δ / β, Δ \cdot β\ ) . We also analyze the theoretical properties of wireless expanders and their connection to unique neighbor expanders, and then demonstrate their applicability: Our results (both the positive and the negative) yield improved bounds for the spokesmen election problem that was introduced in the seminal paper of Chlamtac and Weinstein from 1991 to devise efficient broadcasting for multihop radio networks. Our negative result yields a significantly simpler proof than that from the seminal paper of Kushilevitz and Mansour from 1998 for a lower bound on the broadcast time in radio networks.

In 1999, Brodal and Fagerberg (BF) gave an algorithm for maintaining a low outdegree orientation of a dynamic uniformly sparse graph. Specifically, for a dynamic graph on n -vertices, with arboricity bounded by α at all times, the BF algorithm supports edge updates in $O(łog n)$ amortized update time, while keeping the maximum outdegree in the graph bounded by $O(α)$. Such an orientation provides a basic data structure for uniformly sparse graphs, which found applications to a plethora of dynamic graph algorithms. A significant weakness of the BF algorithm is the possible temporary blowup of the maximum outdegree, following edge insertions. Although BF eventually reduces all outdegrees to $O(α)$, some vertices may reach an outdegree of $Ømega(n)$ during the process, hence local memory usage at the vertices--an important quality measure in distributed systems--cannot be bounded. We show how to modify the BF algorithm to guarantee that the outdegrees of all vertices are bounded by $O(α)$ at all times, without hurting any of its other properties, and present an efficient distributed implementation of the modified algorithm. This provides the first representation of distributed networks in which the local memory usage at vertices is bounded by the arboricity (which is essentially the average degree of the densest subgraph) rather than the maximum degree. For settings where there is no local memory constraints, one may take the temporary outdegree blowup to the extreme and allow a permanent outdegree blowup. This allows us to address the second significant weakness of the BF algorithm -- its inherently global nature: An insertion of an edge $(u,v)$ may trigger changes in the orientations of edges that are arbitrarily far away from u and v . We suggest an alternative local scheme, which does not guarantee any outdegree bound on the vertices, yet is just as efficient as the BF scheme for some applications. For example, we obtain a local dynamic algorithm for maintaining a maximal matching with sub-logarithmic update time in uniformly sparse networks, providing an exponential improvement over the state-of-the-art in this context.

A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in O(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs?

Baswana, Gupta and Sen [FOCS'11] showed that fully dynamic maximal matching can be maintained in general graphs with logarithmic amortized update time. More specifically, starting from an empty graph on n fixed vertices, they devised a randomized algorithm for maintaining maximal matching over any sequence of t edge insertions and deletions with a total runtime of O(t log n) in expectation and O(t log n + n log2n) with high probability. Whether or not this runtime bound can be improved towards O(t) has remained an important open problem. Despite significant research efforts, this question has resisted numerous attempts at resolution even for basic graph families such as forests. In this paper, we resolve the question in the affirmative, by presenting a randomized algorithm for maintaining maximal matching in general graphs with constant amortized update time. The optimal runtime bound O(t) of our algorithm holds both in expectation and with high probability. As an immediate corollary, we can maintain 2-approximate vertex cover with constant amortized update time. This result is essentially the best one can hope for (under the unique games conjecture) in the context of dynamic approximate vertex cover, culminating a long line of research. Our algorithm builds on Baswana et al.'s algorithm, but is inherently different and arguably simpler. As an implication of our simplified approach, the space usage of our algorithm is linear in the (dynamic) graph size, while the space usage of Baswana et al.'s algorithm is always at least Ω(n log n). Finally, we present applications to approximate weighted matchings and to distributed networks.

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 existentially optimal (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 O(n log n)-time construction of (1+epsilon)-spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is O(n log2 n) and whose number of edges and degree are unbounded, and remarkably, it matches the state-of-the-art Euclidean result (due to Gudmundsson et al. [SICOMP'02]) in all the involved parameters (up to dependencies on epsilon and the dimension).

A distributed task is local if its time complexity is (nearly) constant, otherwise it is global. Unfortunately, local tasks are relatively scarce, and most distributed tasks require time at least logarithmic in the network size (and often higher than that). In a dynamic setting, i.e., when the network undergoes repeated and frequent topological changes, such as vertex and edge insertions and deletions, it is desirable to be able to perform a local update procedure around the modified part of the network, rather than running a static global algorithm from scratch following each change. This paper makes a step towards establishing the hypothesis that many (statically) non-local distributed tasks are local-on-average in the dynamic setting, namely, their amortized time complexity is O(log* n). Towards establishing the plausibility of this hypothesis, we propose a strategy for transforming static O(polylog(n)) time algorithms into dynamic O(log* n) amortized time update procedures. We then demonstrate the usefulness of our strategy by applying it to several fundamental problems whose static time complexity is logarithmic, including forest-decomposition, edge-orientation and coloring sparse graphs, and show that their amortized time complexity in the dynamic setting is indeed O(log* n).

Approximate matchings in fully dynamic graphs have been intensively studied in recent years. Gupta and Peng [FOCS'13] presented a deterministic algorithm for maintaining fully dynamic (1 + ∊)-approximate maximum cardinality matching (MCM) in general graphs with worst-case update time , for any ∊ > 0, where m denotes the current number of edges in the graph. Despite significant research efforts, this update time barrier remains the state-of-the-art even if amortized time bounds and randomization are allowed or the approximation factor is allowed to increase from 1 + ∊ to 2 – ∊, and even in basic graph families such as planar graphs. This paper presents a simple deterministic algorithm whose performance depends on the density of the graph. Specifically, we maintain fully dynamic (1 + ∊)-approximate MCM with worst-case update time O(α · ∊–2) for graphs with arboricity1 bounded by α. The update time bound holds even if the arboricity bound α changes dynamically. Since the arboricity ranges between 1 and , our density-sensitive bound O(α ·∊–2) naturally generalizes the bound of Gupta and Peng. For the family of bounded arboricity graphs (which includes forests, planar graphs, and graphs excluding a fixed minor), in the regime ∊ = O(1) our update time reduces to a constant. This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve either an O(log n) worst-case bound (Kopelowitz et al, ICALP'14) or an amortized bound (He et al., ISAAC'14), where n stands for the number of vertices in the graph. En route to this result, we provide local algorithms of independent interest for maintaining fully dynamic approximate matching and vertex cover.

It is long known that for every weighted undirected n -vertex m -edge graph G = ( V , E , ω), and every integer k ⩾ 1, there exists a ((2 k − 1) · (1 + ϵ))-spanner with O ( n 1 + 1/ k ) edges and weight O ( k · n 1/ k · ω( MST ( G )), for an arbitrarily small constant ϵ > 0. (Here ω( MST ( G )) stands for the weight of the minimum spanning tree of G .) To our knowledge, the only algorithms for constructing sparse and lightweight spanners for general graphs admit high running times. Most notable in this context is the greedy algorithm of Althöfer et al. [1993], analyzed by Chandra et al. [1992], which requires O ( m · ( n 1 + 1/ k + n · log n )) time. In this article, we devise an efficient algorithm for constructing sparse and lightweight spanners. Specifically, our algorithm constructs ((2 k − 1) · (1 + ϵ))-spanners with O ( k · n 1 + 1/ k ) edges and weight O ( k · n 1/ k ) · ω( MST ( G )), where ϵ > 0 is an arbitrarily small constant. The running time of our algorithm is O ( k · m + min { n · log n , m · α( n )}). Moreover, by slightly increasing the running time we can reduce the other parameters. These results address an open problem by Roditty and Zwick [2004].

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n -vertex graphs using a trivial deterministic algorithm with a worst-case update time of O ( n ). No deterministic algorithm that outperforms the naïve O ( n ) one was reported up to this date. The only progress in this direction is due to Ivković and Lloyd, who in 1993 devised a deterministic algorithm with an amortized update time of O (( n + m ) √2/2 ), where m is the number of edges. In this article, we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic worst-case update time of O (√ m ). Moreover, our algorithm maintains a matching, which in fact is a 3/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2 − ϵ)-approximate MCM improving upon the naïve O ( n ) was known prior to this work, even allowing amortized time bounds and randomization. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with sublogarithmic update time. Specifically, it maintains a fully dynamic maximal matching with amortized update time of O (log n /log log n ). This result addresses an open question of Onak and Rubinfeld [2010]. We also show a deterministic algorithm with optimal space usage, which for arbitrary graphs maintains a maximal matching in amortized O (√ m ) time and uses only O ( n + m ) space.

The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC'95 paper, titled “Euclidean spanners: short, thin and lanky”, Arya et al. [1995] devised a construction of Euclidean (1+ε)-spanners that achieves constant degree, diameter O (log n ), weight O (log 2 n ) ċ ω( MST ), and has running time O ( n ċ log n ). This construction applies to n -point constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time. This conjecture of Arya et al. became one of the most central open problems in the area of Euclidean spanners. Nevertheless, the only progress since 1995 towards its resolution was achieved in the lower bounds front: Any spanner with diameter O (log n ) must incur weight Ω(log n ) ċ ω( MST ), and this lower bound holds regardless of the stretch or the degree of the spanner [Dinitz et al. 2008; Agarwal et al. 2005]. In this article we resolve the long-standing conjecture of Arya et al. in the affirmative. We present a spanner construction with the same stretch, degree, diameter, and running time, as in Arya et al.'s result, but with optimal weight O (log n ) ċ ω( MST ). So our spanners are as thin and lanky as those of Arya et al., but they are really short! Moreover, our result is more general in three ways. First, we demonstrate that the conjecture holds true not only in constant-dimensional Euclidean spaces, but also in doubling metrics . Second, we provide a general trade-off between the three involved parameters, which is tight in the entire range . Third, we devise a transformation that decreases the lightness of spanners in general metrics , while keeping all their other parameters in check. Our main result is obtained as a corollary of this transformation.

In a seminal STOC 1995 paper, Arya et al. conjectured that spanners for low-dimensional Euclidean spaces with constant maximum degree, hop-diameter $O(\log n)$, and lightness $O(\log n)$ (i.e., weight $O(\log n) \cdot w({MST}))$ can be constructed in $O(n \log n)$ time. This conjecture, which became a central open question in this area, was resolved in the affirmative by Elkin and Solomon in STOC 2013. In fact, Elkin and Solomon proved that the conjecture of Arya et al. holds even in doubling metrics. However, Elkin and Solomon's spanner construction is complicated. In this work we present a significantly simpler construction of spanners for doubling metrics with the same guarantees as above. Our construction is based on the basic net-tree spanner framework. However, by employing well-known properties of the net-tree spanner in conjunction with numerous new ideas, we managed to get significantly stronger results. First and foremost, our construction extends in a simple and natural way to provide $k$-fault tolerant spanners with maximum degree $O(k^2)$, hop-diameter $O(\log n)$, and lightness $O(k^2 \log n)$. This is the first construction of fault-tolerant spanners (even for Euclidean metrics) that achieves good bounds (polylogarithmic in $n$ and polynomial in $k$) on all the involved parameters simultaneously. Second, we show that the lightness bound of our construction can be improved to $O(k^2)$ (with high probability), for random points in $[0,1]^D$, where $2 \le D = O(1)$.

For a pair of parameters $\alpha,\beta \ge 1$, a spanning tree $T$ of a weighted undirected $n$-vertex graph $G = (V,E,w)$ is called an $(\alpha,\beta)$-shallow-light tree (shortly, $(\alpha,\beta)$-SLT) of $G$ with respect to a designated vertex $rt \in V$ if (1) it approximates all distances from $rt$ to the other vertices up to a factor of $\alpha$, and (2) its weight is at most $\beta$ times the weight of the minimum spanning tree $MST(G)$ of $G$. The parameter $\alpha$ (resp., $\beta$) is called the root-distortion (resp., lightness) of the tree $T$. Shallow-light trees (SLTs) constitute a fundamental graph structure, with numerous theoretical and practical applications. In particular, they were used for constructing spanners in network design, for VLSI-circuit design, for various data gathering and dissemination tasks in wireless and sensor networks, in overlay networks, and in the message-passing model of distributed computing. Tight tradeoffs between the parameters of SLTs were established by Awerbuch, Baratz, and Peleg [Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing (PODC), 1990, pp. 177--187, Efficient Broadcast and Light-Weight Spanners, manuscript, 1991] and Khuller, Raghavachari, and Young [Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 1993, pp. 243--250]. They showed that for any $\epsilon > 0$ there always exist $(1+\epsilon,O(\frac{1}{\epsilon}))$-SLTs and that the upper bound $\beta = O(\frac{1}{\epsilon})$ on the lightness of SLTs cannot be improved. In this paper we show that using Steiner points one can build SLTs with logarithmic lightness, i.e., $\beta = O(\log \frac{1}{\epsilon})$. This establishes an exponential separation between spanning SLTs and Steiner ones. In the regime $\epsilon = 0$ our construction provides a shortest-path tree with weight at most $O(\log n) \cdot w(MST(G))$. Moreover, we prove matching lower bounds that show that all our results are tight up to constant factors.

A $t$-spanner of a weighted undirected graph $G=(V,E)$, is a subgraph $H$ such that $d_H(u,v)\le t\cdot d_G(u,v)$ for all $u,v\in V$. The sparseness of the spanner can be measured by its size (the number of edges) and weight (the sum of all edge weights), both being important measures of the spanner's quality; in this work we focus on the latter. Specifically, it is shown that for any parameters $k\ge 1$ and $\varepsilon>0$, any weighted graph $G$ on $n$ vertices admits a $(2k-1)\cdot(1+\varepsilon)$-stretch spanner of weight at most $w(MST(G))\cdot O_\varepsilon(kn^{1/k}/\log k)$, where $w(MST(G))$ is the weight of a minimum spanning tree of $G$. Our result is obtained via a novel analysis of the classic greedy algorithm and improves previous work by a factor of $O(\log k)$.

A classic result in the study of spanners is the existence of light low-stretch spanners for Euclidean spaces. These spanners have arbitrary low stretch, and weight only a constant factor greater than that of the minimum spanning tree of the points (with dependence on the stretch and Euclidean dimension). A central open problem in this field asks whether other spaces admit low weight spanners as well -- for example metric space with low intrinsic dimension -- yet only a handful of results of this type are known.

A spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree is called a shallow-light tree (shortly, SLT). More specifically, an (α, β)-SLT of a weighted undirected graph G = (V, E, w) with respect to a designated vertex rt ∈ V is a spanning tree of G with:

A (1+ε)-spanner for a doubling metric (X, δ) is a subgraph H of the complete graph corresponding to (X, δ), which preserves all pairwise distances to within a factor of 1 + ε. A natural requirement from a spanner, which is essential for many applications (mainly in distributed systems or wireless networks), is to be robust against vertex and edge failures -- so that even when some vertices and edges in the network fail, we still have a (1 + ε)-spanner for what remains. The spanner H is called a k-fault-tolerant (1 + ε)-spanner, for 1 ≤ k ≤ n -- 2, if for any F ⊆ X with |F| ≤ k, the graph H -- F (obtained by removing from H the vertices of F and their incident edges) is a (1 + ε)-spanner for X -- F.

In a seminal paper from 1995, Arya et al. [Euclidean spanners: Short, thin, and lanky, in Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM, New York, 1995, pp. 489--498] devised a construction that, for any set $S$ of $n$ points in $\mathbb R^d$ and any $\epsilon > 0$, provides a $(1+\epsilon)$-spanner with diameter $O(\log n)$, weight $O(\log^2 n) \cdot w(MST(S))$, and constant maximum degree. Another construction from the same work provides a $(1+\epsilon)$-spanner with $O(n)$ edges and diameter $O(\alpha(n))$, where $\alpha$ stands for the inverse Ackermann function. There are also a few other known constructions of $(1+\epsilon)$-spanners. Das and Narasimhan [A fast algorithm for constructing sparse Euclidean spanners, in Proceedings of the 10th Annual ACM Symposium on Computational Geometry (SOCG), ACM, New York, 1994, pp. 132--139] devised a construction with constant maximum degree and weight $O(w(MST(S)))$, but the diameter may be arbitrarily large. In another construction by Arya et al., there is diameter $O(\log n)$ and weight $O(\log n) \cdot w(MST(S))$, but this construction may have arbitrarily large maximum degree. While these constructions address some important practical scenarios, they fail to address situations in which we are prepared to compromise on one of the parameters but cannot afford for this parameter to be arbitrarily large. In this paper we devise a novel unified construction that trades gracefully among the maximum degree, diameter, and weight. For a positive integer $k$ our construction provides a $(1+\epsilon)$-spanner with maximum degree $O(k)$, diameter $O(\log_k n + \alpha(k))$, weight $O(k \cdot \log_k n \cdot \log n) \cdot w(MST(S))$, and $O(n)$ edges. Note that for $k = O(1)$ this gives rise to maximum degree $O(1)$, diameter $O(\log n)$, and weight $O(\log^2 n) \cdot w(MST(S))$, which is one of the aforementioned results of Arya et al. For $k= n^{1/\alpha(n)}$ this gives rise to diameter $O(\alpha(n))$, weight $O(n^{1/\alpha(n)} \cdot \log n \cdot \alpha(n)) \cdot w(MST(S))$, and maximum degree $O(n^{1/\alpha(n)})$. In the corresponding result from Arya et al., the spanner has the same number of edges and diameter, but its weight and degree may be arbitrarily large. Our bound of $O(\log_k n + \alpha(k))$ on the diameter is optimal under the constraints that the maximum degree is $O(k)$ and the number of edges is $O(n)$. Similarly to the bound of Arya et al., our bound on the weight is optimal up to a factor of $\log n$. Our construction also provides a similar trade-off in the complementary range of parameters, i.e., when the weight should be smaller than $\log^2 n$, but the diameter is allowed to grow beyond $\log n$. Moreover, all our results apply to doubling metrics. En route to these results we devise optimal constructions of 1-spanners for general tree metrics, and we employ them to build our Euclidean spanners. Subsequent papers have utilized our constructions of 1-spanners for tree metrics to resolve a long-standing conjecture of Arya et al.

Since the pioneering works of Peleg and Schäffer [32], Althöfer et al. [4], and Chandra et al. [13], it is known that for every weighted undirected n-vertex m-edge graph G = (V, E), and every integer k ≥ 1, there exists a ((2k − 1) • (1 + ∊))-spanner with O(n1+1/k) edges and weight O(k · n1/k) · ω(MST(G)), for an arbitrarily small constant ∊ > 0. (Here ω(M ST (G)) stands for the weight of the minimum spanning tree of G.) Nearly linear time algorithms for constructing (2k − 1)-spanners with nearly O(n1+1/k) edges were devised in [11, 38, 37]. However, these algorithms fail to guarantee any meaningful upper bound on the weight of the constructed spanners. To our knowledge, there are only two known algorithms for constructing sparse and light spanners for general graphs. One of them is the greedy algorithm of Althöfer et al. [4], analyzed by Chandra et al. [13]. The drawback of the greedy algorithm is that it requires O(m · (n1+1/ + n · log n)) time. The other algorithm is due to Awerbuch et al. [7], from 1991. It constructs O(k)-spanners with O(k · n1+1/k · λ) edges, weight O(k2 · n1/k · λ) · ω(MST(G)), within time O(m · k · n1/k · λ), where λ is the logarithm of the aspect ratio of the graph. The running time of both these algorithms is unsatisfactory. Moreover, the usually faster algorithm of [7] pays for the speedup by significantly increasing both the stretch, the sparsity, and the weight of the resulting spanner. In this paper we devise an efficient algorithm for constructing sparse and light spanners. Specifically, our algorithm constructs ((2k − 1) · (1 + ∊))-spanners with O(k · n1+1/k) edges and weight O(k · n1/k) · ω(MST(G)), where ∊ > 0 is an arbitrarily small constant. The running time of our algorithm is O(k · m + min{n · log n, m · α(n)}). Moreover, by slightly increasing the running time we can reduce the other parameters. These results address an open problem from the ESA'04 paper by Roditty and Zwick [38].

The degree, the (hop-)diameter, and the weight are the most basic and well-studied parameters of geometric spanners. In a seminal STOC'95 paper, titled "Euclidean spanners: short, thin and lanky", Arya et al. [2] devised a construction of Euclidean (1+ε)-spanners that achieves constant degree, diameter O(log n), weight O(log2 n) ⋅ ω(MST), and has running time O(n ⋅ log n). This construction applies to n-point constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time.

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the naive O(n) one was reported up to this date. The only progress in this direction is due to Ivkovic and Lloyd [14], who in 1993 devised a deterministic algorithm with an amortized update time of O((n+m)√2/2), where m is the number of edges.

In STOC’95, Arya et al. [1995] showed that for any set of n points in R d , a (1 + ε )-spanner with diameter at most 2 (respectively, 3) and O ( n log n ) edges (respectively, O ( n log log n ) edges) can be built in O ( n log n ) time. Moreover, it was shown in Arya et al. [1995] and Narasimhan and Smid [2007] that for any k ≥ 4, one can build in O ( n (log n )2 k α k ( n )) time a (1 + ε )-spanner with diameter at most 2 k and O ( n 2 k α k ( n )) edges. The function α k is the inverse of a certain function at the k /2 th level of the primitive recursive hierarchy, where α 0 ( n ) = n /2 , α 1 ( n ) = √ n , α 2 ( n ) = log n , α 3 ( n ) = log log n , α 4 ( n ) = log* n , α 5 ( n ) = 12 log* n , ..., etc. It is also known [Narasimhan and Smid 2007] that if one allows quadratic time, then these bounds can be improved. Specifically, for any k ≥ 4, a (1 + ε )-spanner with diameter at most k and O ( nkα k ( n )) edges can be constructed in O ( n 2 ) time [Narasimhan and Smid 2007]. A major open question in this area is whether one can construct within time O ( n log n + nkα k ( n )) a (1 + ε )-spanner with diameter at most k and O ( nkα k ( n )) edges. In this article, we answer this question in the affirmative. Moreover, in fact, we provide a stronger result. Specifically, we show that for any k ≥ 4, a (1 + ε )-spanner with diameter at most k and O ( nα k ( n )) edges can be built in optimal time O ( n log n ).

Consider an n-point metric space $M = (V,\delta)$ and a transmission range assignment $r: V \rightarrow \mathbb R^+$ that maps each point $v \in V$ to the disk of radius $r(v)$ around it. The symmetric disk graph (SDG) that corresponds to M and r is the undirected graph over V whose edge set includes an edge $(u,v)$ if both $r(u)$ and $r(v)$ are no smaller than $\delta(u,v)$. SDGs are often used to model wireless communication networks. Abu-Affash et al. [Lecture Notes in Comput. Sci. 6139, Springer, Heidelberg, 2010, pp. 236–247] showed that for any n-point 2-dimensional Euclidean space M, the weight of the minimum spanning tree (MST) of every connected SDG for M is $O(\log n) \cdot w(MST(M))$, and that this bound is tight. However, the upper bound proof of Abu-Affash et al. relies heavily on basic geometric properties of constant-dimensional Euclidean spaces and does not extend to Euclidean spaces of super-constant dimension. A natural question that arises is whether this surprising upper bound of Abu-Affash et al. can be generalized for wider families of metric spaces, such as high-dimensional Euclidean spaces. In this paper we generalize the upper bound of Abu-Affash et al. for Euclidean spaces of any dimension. Furthermore, our upper bound extends to arbitrary metric spaces and, in particular, it applies to any of the normed spaces $\ell_p$. Specifically, we demonstrate that for any n-point metric space M, the weight of the MST of every connected SDG for M is $O(\log n) \cdot w(MST(M))$.

For a pair of parameters α, β ≥ 1, a spanning tree T of a weighted undirected n-vertex graph G = (V, E, w) is called an (α,β)-shallow-light tree (shortly, (α,β-SLT) of G with respect to a designated vertex rt ∈ V if (1) it approximates all distances from rt to the other vertices up to a factor of α, and (2) its weight is at most β times the weight of the minimum spanning tree MST(G) of G. The parameter α (respectively, β) is called the root-distortion (resp., lightness) of the tree T. Shallow-light trees (SLTs) constitute a fundamental graph structure, with numerous theoretical and practical applications. In particular, they were used for constructing spanners, in network design, for VLSI-circuit design, for various data gathering and dissemination tasks in wireless and sensor networks, in overlay networks, and in the message-passing model of distributed computing. Tight tradeoffs between the parameters of SLTs were established by Awer buch et al. [5], [6] and Khuller et al. [33]. They showed that for any ϵ >; 0 there always exist (1+ϵ, O(1/ϵ))-SLTs, and that the upper bound β = O(1/ϵ) on the lightness of SLTs cannot be improved. In this paper we show that using Steiner points one can build SLTs with logarithmic lightness, i.e., β = O(log 1/ϵ). This establishes an exponential separation between spanning SLTs and Steiner ones. One particularly remarkable point on our tradeoff curve is ϵ = 0. In this regime our construction provides a shortest-path tree with weight at most O(log n) · w(MST(G)). Moreover, we prove matching lower bounds that show that all our results are tight up to constant factors. Finally, on our way to these results we settle (up to constant factors) a number of open questions that were raised by Khuller et al. [33] in SODA'93.

In STOC'95 [5] Arya et al. showed that for any set of n points in ℝd, a (1 + ∊)-spanner with diameter at most 2 (respectively 3) and O(n log n) edges (resp., O(n log log n) edges) can be built in O(n log n) time. Moreover, Arya et al. [5] conjectured that one can build in O(n log n) time a (1 + ∊)-spanner with diameter at most 4 and O(n log* n) edges. Since then, this conjecture became a central open problem in this area. Nevertheless, very little progress on this problem was reported up to this date. In particular, the previous state-of-the-art subquadratic-time construction of (1 + ∊)-spanners with o(n log log n) edges due to Arya et al. [5] produces spanners with diameter 8.

We show that for every set $\mathcal{S}$ of n points in the plane and a designated point $rt\in\mathcal{S}$, there exists a tree T that has small maximum degree, depth, and weight. Moreover, for every point $v\in\mathcal{S}$, the distance between $rt$ and v in T is within a factor of $(1+\epsilon)$ close to their Euclidean distance $\|rt,v\|$. We call these trees narrow-shallow-low-light (NSLLTs). We demonstrate that our construction achieves optimal (up to constant factors) tradeoffs between all parameters of NSLLTs. Our construction extends to point sets in $\mathbb{R}^d$ for an arbitrarily large constant d. The running time of our construction is $O(n\cdot\log n)$. We also study this problem in general metric spaces, and show that NSLLTs with small maximum degree, depth, and weight can always be constructed if one is willing to compromise the root-distortion. On the other hand, we show that the increased root-distortion is inevitable, even if the point set $\mathcal{S}$ resides in a Euclidean space of dimension $\Theta(\log n)$. In addition, we show that if one is allowed to use Steiner points, then it is possible to achieve root-distortion of $(1+\epsilon)$ together with small maximum degree, depth, and weight for general metric spaces. Finally, we establish some lower bounds on the power of Steiner points in the context of Euclidean spanning trees and spanners.

We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O(k) and weight w(T) = O(k ldr n1/k)ldrw(MST(M)), and a spanning tree T' with weight w(T') = O(k)ldrw(MST(M)) and unweighted diameter O(k ldr n1/k). Moreover, there is a designated point rt such that for every other point v, both distT(rt, v) and distT(rt, v) are at most (1 + epsiv)ldrdistM(rt,v), for an arbitrarily small constant epsiv > 0. We prove that the above tradeoffs are tight up to constant factors in the entire range of parameters. Furthermore, our lower bounds apply to a basic one-dimensional Euclidean space. Finally, our lower bounds for the particular case of unweighted diameter O(log n) settle a long-standing open problem in Computational Geometry.

The Tower of Hanoi problem is generalized by placing pegs on the vertices of a given directed graph G with two distinguished vertices, S and D , and allowing moves only along arcs of this graph. An optimal solution for such a graph G is an algorithm that completes the task of moving a tower of any given number of disks from S to D in a minimal number of disk moves. In this article we present an algorithm which solves the problem for two infinite families of graphs, and prove its optimality. To the best of our knowledge, this is the first optimality proof for an infinite family of graphs. Furthermore, we present a unified algorithm that solves the problem for a wider family of graphs and conjecture its optimality.

We study the Bottleneck Tower of Hanoi puzzle posed by D. Wood in 1981. There, a relaxed placement rule allows a larger disk to be placed higher than a smaller one if their size difference is less than a pregiven value k . A shortest sequence of moves (optimal algorithm) transferring all the disks placed on some peg in decreasing order of size, to another peg in the same order is in question. In 1992, D. Poole suggested a natural disk-moving strategy for this problem, and computed the length of the shortest move sequence under its framework. However, other strategies were overlooked, so the lower bound/optimality question remained open. In 1998, Benditkis, Berend, and Safro proved the optimality of Poole's algorithm for the first nontrivial case k = 2. We prove Poole's algorithm to be optimal in the general case.