Memory-(in)efficiency is a crucial consideration that oftentimes prevents deployment of state-of-the-art distributed algorithms in real-life modern networks. In the context of the MST problem, roughly speaking, there are three types of algorithms. The GHS algorithm (Gallager et al. 1983) and its versions are memory- and message-efficient, but their running time is at least linear in the number of vertices n, even when the unweighted diameter D is much smaller than n. The GKP algorithm (Garay et al. 1998) and its versions are time-efficient, but not message- or memory-efficient. Several recent algorithms (Elkin 2020, Haeupler et al. 2018, Pandurangan et al. 2020) are time- and message-efficient, but are not memory-efficient. GHS-type algorithms are much more prominent in real-life applications, in part due to their relative simplicity, but also because memory-efficiency acts as a constraint. In this paper we develop a deterministic time-, message- and memory-efficient algorithm for the MST problem. Our algorithm is also applicable to the more general partwise aggregation problem. We believe that our techniques will be useful for devising memory-efficient algorithms to many other distributed problems.

We study the (Δ + 1)-edge-coloring problem in the parallel (PRAM) model of computation. The celebrated Vizing's theorem [Viz64] states that every simple graph G = (V, E) can be properly (Δ + 1)-edge-colored. In a seminal paper, Karloff and Shmoys [KS87] devised a parallel algorithm with time O(Δ5 · log n · (log3 n + Δ2)) and O(m · Δ) processors. This result was improved by Liang et al. [LSH96] to time O(Δ4.5 · log3 Δ · log n + Δ4 · log4n) and O(n • Δ3 + n2) processors. [LSH96] claimed O(Δ3.5 · log3 Δ · log n + Δ3 • log4 n) time, but we point out a flaw in their analysis, which once corrected, results in the above bound. We devise a faster parallel algorithm for this fundamental problem. Specifically, our algorithm uses O(Δ4 · log4 n) time and O(m · Δ) processors. Another variant of our algorithm requires O(Δ4+o(1) · log2 n) time, and [EQUATION] processors, for an arbitrarily small δ > 0. We also devise a few other tradeoffs between the time and the number of processors, and devise an improved algorithm for graphs with small arboricity. On the way to these results, we also provide a very fast parallel algorithm for updating (Δ + 1)-edge-coloring. Our algorithm for this problem is dramatically faster and simpler than the previous state-of-the-art algorithm (due to [LSH96]) for this problem.

Given an n-vertex undirected graph $G=(V, E, w)$ and a parameter $k \geq 1$, a path-reporting distance oracle (or PRDO) is a data structure of size $S(n, k)$, that given a query $(u, v) \in V^{2}$, returns an $f(k)$-approximate shortest $u-v$ path P in G within time $q(k)+O(|P|)$. Here $S(n, k), f(k)$ and $q(k)$ are arbitrary (hopefully slowly-growing) functions. A distance oracle that only returns an approximate estimate $\hat{d}(u, v)$ of the distance $d_{G}(u, v)$ between the queried vertices is called a nonpath-reporting distance oracle.A landmark PRDO due to Thorup and Zwick [56] has $S(n, k)=O\left(k \cdot n^{1+\frac{1}{k}}\right), f(k)=2 k-1$ and $q(k)=O(k)$. Wulff-Nilsen [59] devised an improved query algorithm for this oracle with $q(k)=O(\log k)$. The size of this oracle is $\Omega(n \log n)$ for all k. Elkin and Pettie [30] devised a PRDO with $S(n, k)=O\left(\log k \cdot n^{1+\frac{1}{k}}\right), f(k)=O\left(k^{\log _{4 / 3} 7}\right)$ and $q(k)=O(\log k)$. Neiman and Shabat [46] recently devised an improved PRDO with $S(n, k)=O\left(n^{1+\frac{1}{k}}\right), f(k)=O\left(k^{\log _{4 / 3} 4}\right)$ and $q(k)=O(\log k)$. These oracles (of [30], [46]) can be much sparser than $O(n \log n)$ (the oracle of [46] can have linear size), but their stretch is polynomially larger than the optimal bound of $2 k-1$. On the other hand, a long line of non-pathreporting distance oracles culminated in a celebrated result by Chechik [14], in which $S(n, k)=O\left(n^{1+\frac{1}{k}}\right), f(k)=2 k-1$ and $q(k)=O(1)$.In this paper we make a dramatic progress in bridging the gap between path-reporting and non-path-reporting distance oracles. In particular, we devise a PRDO with size $S(n, k)=$ $O\left(\left[\frac{k \cdot \log \log n}{\log n}\right] \cdot n^{1+\frac{1}{k}}\right)$, stretch $f(k)=O(k)$ and query time $q(k)=O\left(\log \left\lceil\frac{k \cdot \log \log n}{\log n}\right\rceil\right)$. As $\left\lceil\frac{k \cdot \log \log n}{\log n}\right\rceil=O(\log k)$ for $k \leq \log n$, its size is always at most $O\left(\log k \cdot n^{1+\frac{1}{k}}\right)$, and its query time is $O(\log \log k)$. Moreover, for $k=O\left(\frac{\log n}{\log \log n}\right)$, we have $\left[\frac{k \cdot \log \log n}{\log n}\right]=O(1)$, i.e., $S(n, k)=O\left(n^{1+\frac{1}{k}}\right), f(k)=O(k)$, and $q(k)=O(1)$. For $k=\Theta(\log n)$, our oracle has size $O(n \log \log n)$, stretch $O(\log n)$ and query time $O\left(\log ^{(3)} n\right)$. We can also have linear size $O(n)$, stretch $O(\log n \cdot \log \log n)$ and query time $O\left(\log ^{(3)} n\right)$.These trade-offs exhibit polynomial improvement in stretch over the PRDOs of [30], [46]. For $k=\Omega\left(\frac{\log n}{\log \log n}\right)$, our tradeoffs also strictly improve the long-standing bounds of [56], [59].Our results on PRDOs are based on novel constructions of approximate distance preservers, that we devise in this paper. Specifically, we show that for any $\epsilon gt 0$, any $k=1,2, \ldots$, and any graph $G=(V, E, w)$ and a collection $\mathcal{P}$ of p vertex pairs, there exists a $(1+\epsilon)$-approximate preserver for $G, \mathcal{P}$ with $O\left(\gamma(\epsilon, k) \cdot p+n \log k+n^{1+\frac{1}{k}}\right)$ edges, where $\gamma(\epsilon, k)=$ $\left(\frac{\log k}{\epsilon}\right)^{O(\log k)}$. These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter [41].

Graph spanners and emulators are sparse structures that approximately preserve distances of the original graph. While there has been an extensive amount of work on additive spanners, so far little attention was given to weighted graphs. Only very recently as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). extended the classical +2 (respectively, +4) spanners for unweighted graphs of size $$O(n^{3/2})$$ (resp., $$O(n^{7/5})$$ ) to the weighted setting, where the additive error is $$+2W$$ (resp., $$+4W$$ ). This means that for every pair u, v, the additive stretch is at most $$+2W_{u,v}$$ , where $$W_{u,v}$$ is the maximal edge weight on the shortest $$u-v$$ path (weights are normalized so that the minimum edge weight is 1). In addition, as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). showed a randomized algorithm yielding a $$+8W_{max}$$ spanner of size $$O(n^{4/3})$$ , here $$W_{max}$$ is the maximum edge weight in the entire graph. In this work we improve the latter result by devising a simple deterministic algorithm for a $$+(6+\varepsilon )W$$ spanner for weighted graphs with size $$O(n^{4/3})$$ (for any constant $$\varepsilon >0$$ ), thus nearly matching the classical +6 spanner of size $$O(n^{4/3})$$ for unweighted graphs. Furthermore, we show a $$+(2+\varepsilon )W$$ subsetwise spanner of size $$O(n\cdot \sqrt{\vert S\vert })$$ , improving the $$+4W_{max}$$ result of as reported by Ahmed et al. (in: Adler I, Müller H (eds) Graph-Theoretic Concepts in Computer Science - 46th International Workshop, WG 2020, Leeds, UK). (that had the same size). We also show a simple randomized algorithm for a $$+4W$$ emulator of size $${\tilde{O}}(n^{4/3})$$ . In addition, we show that our technique is applicable for very sparse additive spanners, that have linear size. It was proved by Abboud A, Bodwin G (J ACM 64(4):28–12820 2017) that such spanners must suffer polynomially large stretches. For weighted graphs, we use a variant of our simple deterministic algorithm that yields a linear size $$+{\tilde{O}}(\sqrt{n}\cdot W)$$ spanner, and we also obtain a tradeoff between size and stretch. Finally, generalizing the technique of Dor D et al. (SIAM J Comput 29:1740–1759, 2000) for unweighted graphs, we devise an efficient randomized algorithm producing a $$+2W$$ spanner for weighted graphs of size $${\tilde{O}}(n^{3/2})$$ in $${\tilde{O}}(n^2)$$ time.

Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of 2κ - 1 versus n 1+1/κ, for an integer parameter κ. (In fact, existing solutions also incur an extra factor of 1 + ϵ in the stretch for weighted graphs, and an additional factor of log O(1) n in the space.) The only existing solution of the second type uses n 1/2-O(1/κ) passes over the stream (for space O(n 1+1/κ)), and applies only to unweighted graphs. In this paper we show that (1 + ϵ)-approximate single-source shortest paths can be computed with Õ(n 1+1/κ) space using just constantly many passes in unweighted graphs, and polylogarithmically many passes in weighted graphs. Moreover, the same result applies for multi-source shortest paths, as long as the number of sources is O(n 1/κ). We achieve these results by devising efficient dynamic streaming constructions of (1 + ϵ, β)-spanners and hopsets. On our way to these results, we also devise a new dynamic streaming algorithm for the 1-sparse recovery problem. Even though our algorithm for this task is slightly inferior to the existing algorithms of [26, 11], we believe that it is of independent interest.

This paper presents new deterministic and distributed low-diameter decomposition algorithms for weighted graphs. In particular, we show that if one can efficiently compute approximate distances in a parallel or a distributed setting, one can also efficiently compute low-diameter decompositions. This consequently implies solutions to many fundamental distance based problems using a polylogarithmic number of approximate distance computations.Our low-diameter decomposition generalizes and extends the line of work starting from [RG20] to weighted graphs in a very model-independent manner. Moreover, our clustering results have additional useful properties, including strong-diameter guarantees, separation properties, restricting cluster centers to specified terminals, and more. Applications include:–The first near-linear work and polylogarithmic depth randomized and deterministic parallel algorithm for low-stretch spanning trees (LSST) with polylogarithmic stretch. Previously, the best parallel LSST algorithm required $m.n^{o(1)}$ work and $n^{o(1)}$ depth and was inherently randomized. No deterministic LSST algorithm with truly sub-quadratic work and sub-linear depth was known.–The first near-linear work and polylogarithmic depth deterministic algorithm for computing an $\ell_{1}-$embedding into polylogarithmic dimensional space with polylogarithmic distortion. The best prior deterministic algorithms for $\ell_{1}$-embeddings either require large polynomial work or are inherently sequential.Even when we apply our techniques to the classical problem of computing a ball-carving with strong-diameter $O(\log^{2}n)$ in an unweighted graph, our new clustering algorithm still leads to an improvement in round complexity from $O(\log^{10}n)$ rounds [CG21] to $O(\log^{4}n)$.

Computing approximate shortest paths in the dynamic streaming setting is a fundamental challenge that has been intensively studied. Currently existing solutions for this problem either build a sparse multiplicative spanner of the input graph and compute shortest paths in the spanner offline, or compute an exact single source BFS tree. Solutions of the first type are doomed to incur a stretch-space tradeoff of 2k - 1 versus n1+1/k , for an integer parameter k. (In fact, existing solutions also incur an extra factor of 1+ε in the stretch for weighted graphs, and an additional factor of logO(1) n in the space.) The only existing solution of the second type uses n1/2-O(1/k) passes over the stream (for space O(n1+1/k )), and applies only to unweighted graphs.

This paper presents efficient distributed algorithms for a number of fundamental problems in the area of graph sparsification:We provide the first deterministic distributed algorithm that computes an ultra-sparse spanner in polylog(n) rounds in weighted graphs. Concretely, our algorithm outputs a spanning subgraph with only n + o (n) edges in which the pairwise distances are stretched by a factor of at most O(logn · 2O(log* n) ).

Consider an undirected weighted graph G = (V,E,w). We study the problem of computing (1+ε)-approximate shortest paths for S × V, for a subset S ⊆ V of |S| = n^r sources, for some 0 < r ≤ 1. We devise a significantly improved algorithm for this problem in the entire range of parameter r, in both the classical centralized and the parallel (PRAM) models of computation, and in a wide range of r in the distributed (Congested Clique) model. Specifically, our centralized algorithm for this problem requires time Õ(|E| ⋅ n^{o(1)} + n^{ω(r)}), where n^{ω(r)} is the time required to multiply an n^r × n matrix by an n × n one. Our PRAM algorithm has polylogarithmic time (log n)^{O(1/ρ)}, and its work complexity is Õ(|E| ⋅ n^ρ + n^{ω(r)}), for any arbitrarily small constant ρ > 0. In particular, for r ≤ 0.313…, our centralized algorithm computes S × V (1+ε)-approximate shortest paths in n^{2 + o(1)} time. Our PRAM polylogarithmic-time algorithm has work complexity O(|E| ⋅ n^ρ + n^{2+o(1)}), for any arbitrarily small constant ρ > 0. Previously existing solutions either require centralized time/parallel work of O(|E| ⋅ |S|) or provide much weaker approximation guarantees. In the Congested Clique model, our algorithm solves the problem in polylogarithmic time for |S| = n^r sources, for r ≤ 0.655, while previous state-of-the-art algorithms did so only for r ≤ 1/2. Moreover, it improves previous bounds for all r > 1/2. For unweighted graphs, the running time is improved further to poly(log log n) for r ≤ 0.655. Previously this running time was known for r ≤ 1/2.

We consider graph coloring and related problems in the distributed message-passing model.Locally-iterative algorithmsare especially important in this setting. These are algorithms in which each vertex decides about its next color only as a function of the current colors in its1-hop-neighborhood. In STOC’93 Szegedy and Vishwanathan showed that any locally-iterative Δ + 1-coloring algorithm requires Ω (Δ log Δ + log*n) rounds, unless there exists “a very special type of coloring that can be very efficiently reduced” [ 44 ]. No such special coloring has been found since then. This led researchers to believe that Szegedy-Vishwanathan barrier is an inherent limitation for locally-iterative algorithms and to explore other approaches to the coloring problem [ 2 , 3 , 19 , 32 ]. The latter gave rise to faster algorithms, but their heavy machinery that is of non-locally-iterative nature made them far less suitable to various settings. In this article, we obtain the aforementioned special type of coloring. Specifically, we devise a locally-iterative Δ + 1-coloring algorithm with running timeO(Δ + log*n), i.e.,belowSzegedy-Vishwanathan barrier. This demonstrates that this barrier is not an inherent limitation for locally-iterative algorithms. As a result, we also achieve significant improvements for dynamic, self-stabilizing, and bandwidth-restricted settings. This includes the following results: We obtain self-stabilizing distributed algorithms for Δ + 1-vertex-coloring, (2Δ - 1)-edge-coloring, maximal independent set, and maximal matching withO(Δ + log*n) time. This significantly improves previously known results that haveO(n)or larger running times [ 23 ]. We devise a (2Δ - 1)-edge-coloring algorithm in the CONGEST model withO(Δ + log*n) time andO(Δ)-edge-coloring in the Bit-Round model withO(Δ + logn) time. The factors of log*nand lognare unavoidable in the CONGEST and Bit-Round models, respectively. Previously known algorithms had superlinear dependency on Δ for (2Δ - 1)-edge-coloring in these models. We obtain an arbdefective coloring algorithm with running timeO(√ Δ + log*n). Such a coloring is not necessarily proper, but has certain helpful properties. We employ it to compute a proper (1 + ε)Δ-coloring withinO(√ Δ + log*n) time and Δ + 1-coloring withinO(√ Δ log Δ log*Δ + log*n) time. This improves the recent state-of-the-art bounds of Barenboim from PODC’15 [ 2 ] and Fraigniaud et al. from FOCS’16 [ 19 ] by polylogarithmic factors. Our algorithms are applicable to the SET-LOCAL model [ 25 ] (also known as the weak LOCAL model). In this model a relatively strong lower bound of Ω (Δ1/3) is known for Δ + 1-coloring. However, most of the coloring algorithms do not work in this model. (In Reference [ 25 ] only Linial’sO(Δ2)-time algorithm and Kuhn-WattenhoferO(Δ log Δ)-time algorithms are shown to work in it.) We obtain the first linear-in-Δ Δ + 1-coloring algorithms that work also in this model.

Given metric spaces $(X,d)$ and $(Y,\rho)$ and an ordering $x_1,x_2,\ldots,x_n$ of $(X,d)$, an embedding $f: X \rightarrow Y$ is said to have a prioritized distortion $\alpha(\cdot)$, for a function $\alpha(\cdot)$, if for any pair $x_j,x'$ of distinct points in $X$, the distortion provided by $f$ for this pair is at most $\alpha(j)$. If $Y$ is a normed space, the embedding is said to have prioritized dimension $\beta(\cdot)$ if $f(x_j)$ may have at most $\beta(j)$ nonzero coordinates. The notion of prioritized embedding was introduced by Filtser and the current authors in [M. Elkin, A. Filtser, and O. Neiman, SIAM J. Comput., 47 (2018), pp. 829--858], where a rather general methodology for constructing such embeddings was developed. Though this methodology enabled [M. Elkin, A. Filtser, and O. Neiman, SIAM J. Comput., 47 (2018), pp. 829--858] to come up with many prioritized embeddings, it typically incurs some loss in the distortion. In other words, in the worst case, prioritized embeddings obtained via this methodology incur distortion which is at least a constant factor off compared to the distortion of the classical counterparts of these embeddings. This constant loss is problematic for isometric embeddings. It is also troublesome for Matoušek's embedding of general metrics into $\ell_\infty$, which, for a parameter $k = 1,2,\ldots$, provides distortion $2k-1$ and dimension $O(k \log n \cdot n^{1/k})$. All logarithms in this paper are base 2. In this paper we devise two lossless prioritized embeddings. The first one is an isometric prioritized embedding of tree metrics into $\ell_\infty$ with dimension $O(\log j)$, matching the worst-case guarantee of $O(\log n)$ of the classical embedding of [N. Linial, E. London, and Y. Rabinovich, Combinatorica, 15 (1995), pp. 215--245]. The second one is a prioritized Matoušek embedding of general metrics into $\ell_\infty$, which, for a parameter $k=1,2,\ldots$, provides prioritized distortion $2 \lceil k {{\log j} \over {\log n}} \rceil - 1$ and dimension $O(k \log n \cdot n^{1/k})$, again matching the worst-case guarantee $2k-1$ in the distortion of the classical Matoušek embedding. We also provide a dimension-prioritized variant of Matoušek's embedding. Finally, we devise prioritized embeddings of general metrics into a single ultrametric and of general graphs into a single spanning tree, with asymptotically optimal distortion.

Near-additive (aka (1+ε,β)β-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings.

We study a (1+ε)-approximate single-source shortest paths (henceforth, (1+ε)-SSSP) in n-vertex undirected, weighted graphs in the parallel (PRAM) model of computation. A randomized algorithm with polylogarithmic time and slightly super-linear work Õ(|E|• n^ρ), for an arbitrarily small ρ>0, was given by Cohen (10) more than 25 years ago. Exciting progress on this problem was achieved in recent years (4, 17, 19, 35), culminating in randomized polylogarithmic time and Õ(|E|) work. However, the question of whether there exists a deterministic counterpart of Cohen's algorithm remained wide open.

Given a metric space (X, d), a set of terminals $$K\subseteq X$$ , and a parameter $$0<\epsilon <1$$ , we consider metric structures (e.g., spanners, distance oracles, embedding into normed spaces) that preserve distances for all pairs in $$K\times X$$ up to a factor of $$1+\epsilon$$ , and have small size (e.g. number of edges for spanners, dimension for embeddings). While such terminal (aka source-wise) metric structures are known to exist in several settings, no terminal spanner or embedding with distortion close to 1, is currently known. Here we devise such terminal metric structures for doubling metrics, and show that essentially any metric structure with distortion $$1+\epsilon$$ and space s(|X|) has its terminal counterpart, with distortion $$1+O(\epsilon )$$ and space $$s(|K|)+n$$ . In particular, for any doubling metric on n points, a set of k terminals, and constant $$0<\epsilon <1$$ , there exists Moreover, surprisingly, the last two results apply if only the metric space on K is doubling, while the metric on X can be arbitrary.

A t-spanner H of a weighted graph G = (V, E, w) is a subgraph that approximates all pairwise distances up to a factor of t. The lightness of H is defined as the ratio between the weight of H to that of the minimum spanning tree. An (α, β)-Shallow Light Tree (SLT) is a tree of lightness β, that approximates all distances from a designated root vertex up to a factor of α. A long line of works resulted in efficient algorithms that produce (nearly) optimal light spanners and SLTs.

Given metric spaces (X, d) and (Y, ρ) and an ordering x1,x2,…,xn of (X, d), an embedding f: X → Y is said to have a prioritized distortion α(·), for a function α(·), if for any pair xj,x′ of distinct points in X, the distortion provided by f for this pair is at most a(j). If Y is a normed space, the embedding is said to have prioritized dimension β(·), if f(xj) may have at most β(j) nonzero coordinates. The notion of prioritized embedding was introduced by Filtser and the current authors in [EFN18], where a rather general methodology for constructing such embeddings was developed. Though this methodology enabled [EFN18] to come up with many prioritized embeddings, it typically incurs some loss in the distortion. In other words, in the worst-case, prioritized embeddings obtained via this methodology incur distortion which is at least a constant factor off, compared to the distortion of the classical counterparts of these embeddings. This constant loss is problematic for isometric embeddings. It is also troublesome for Matousek's embedding of general metrics into ℓ∞, which for a parameter k = 1, 2, …, provides distortion 2k–1 and dimension O(k log n·n1/k). In this paper we devise two lossless prioritized embeddings. The first one is an isometric prioritized embedding of tree metrics into with dimension O(log j), matching the worst-case guarantee of O(log n) of the classical embedding of Linial et al. [LLR95]. The second one is a prioritized Matousek's embedding of general metrics into ℓ∞, which for a parameter k = 1,2, …, provides prioritized distortion and dimension O(k log n · n1/k), again matching the worst-case guarantee 2k – 1 in the distortion of the classical Matousek's embedding. We also provide a dimension-prioritized variant of Matousek's embedding. Finally, we devise prioritized embeddings of general metrics into (single) ultra-metric and of general graphs into (single) spanning tree with asymptotically optimal distortion.

The distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg devised an algorithm with running time O ( D + √ n ⋅ log * n ), where D is the hop diameter of the input n -vertex m -edge graph, and with message complexity O ( m + n 3/2 ). Peleg and Rubinovich showed that the running time of the algorithm of Kutten and Peleg is essentially tight and asked if one can achieve near-optimal running time together with near-optimal message complexity. In a recent breakthrough, Pandurangan et al. answered this question in the affirmative and devised a randomized algorithm with time Õ ( D + √ n ) and message complexity Õ ( m ). They asked if such a simultaneous time- and message optimality can be achieved by a deterministic algorithm. In this article, building on the work of Pandurangan et al., we answer this question in the affirmative and devise a deterministic algorithm that computes MST in time O (( D + √ n ) ⋅ log n ) using O ( m ⋅ log n + n log n cdot log * n ) messages. The polylogarithmic factors in the time and message complexities of our algorithm are significantly smaller than the respective factors in the result of Pandurangan et al. In addition, our algorithm and its analysis are very simple and self-contained as opposed to rather complicated previous sublinear-time algorithms. Finally, we use our new algorithm to devise a randomized MST algorithm with running time Õ (μ ( G ,ω) + √ n ) and message complexity Õ (| E |), where μ-radius μ ( G ,ω) ≤ D is a graph parameter, which is typically much smaller than D . This improves a previous bound from Elkin.

The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it inO(n) time, wherenis the number of vertices in the input graphG. Peleg and Rubinovich [49] showed a lower bound of ˜Ω(D+ √n) for this problem, whereDis the hop-diameter ofG. Whether or not this problem can be solved inO(n) time whenDis relatively small is a major open question. Despite intensive research [10, 17, 33, 41, 45] that yielded near-optimal algorithms for theapproximatevariant of this problem, no progress was reported for the original problem. In this article, we answer this question in the affirmative. We devise an algorithm that requiresO((nlogn)5/6) time, forD=O(√nlogn), andO(D1/3⋅ (nlogn)2/3) time, for largerD. This running time is sublinear innin almost the entire range of parameters, specifically, forD=o(n/ log2n). We also generalize our result in two directions. One is when edges have bandwidthb≥ 1, and the other is thes-sources shortest paths problem. For both problems, our algorithm provides bounds that improve upon the previous state-of-the-art in almost the entire range of parameters. In particular, we provide an all-pairs shortest paths algorithm that requiresO(n5/3⋅ log2/3n) time, even forb= 1, for all values ofD. We also devise the first algorithm with non-trivial complexity guarantees for computing exact shortest paths in themultipass semi-streamingmodel of computation. From the technical viewpoint, our distributed algorithm computes a hopsetG′′of a skeleton graphG′ofGwithout first computingG′itself. We then conduct a Bellman-Ford exploration inG′∪G′′, while computing the required edges ofG′on the fly. As a result, our distributed algorithm computesexactlythose edges ofG′that it really needs, rather than computing approximately the entireG′.

Given a pair of parameters α ≥ 1,β ≥ 0, a subgraph G'=(V,H) of an n-vertex unweighted undirected graph G=(V,E) is called an (α,β)-spanner if for every pair u,ν ∈ V of vertices, we have dG' (u,ν)≤ α dG (u,α)+β. If β=0 the spanner is called a multiplicative α-spanner, and if α = 1+ε, for an arbitrarily small ε>0, the spanner is said to be near-additive.

For a positive parameter β, the β-bounded distance between a pair of vertices u,v in a weighted undirected graph G = (V,E,ømega) is the length of the shortest u-v path in G with at most β edges, aka hops. For β as above and ε > 0, a (β,ε)-hopset of G = (V,E,ømega) is a graph GH =(V,H,ømegaH) on the same vertex set, such that all distances in G are (1+ε)-approximated by β-bounded distances in G ∪ GH. Hopsets are a fundamental graph-theoretic and graph-algorithmic construct, and they are widely used for distance-related problems in a variety of computational settings. Currently existing constructions of hopsets produce hopsets either with Ømega(n łog n) edges, or with a hopbound nØmega(1). In this paper we devise a construction of linear-size hopsets with hopbound (ignoring the dependence on ε) (łog łog n)łog łog n + O(1). This improves the previous hopbound for linear-size hopsets almost exponentially. We also devise efficient implementations of our construction in PRAM and distributed settings. The only existing PRAM algorithm [11] for computing hopsets with a constant (i.e., independent of n) hopbound requires nØmega(1) time. We devise a PRAM algorithm with polylogarithmic running time for computing hopsets with a constant hopbound, i.e., our running time is exponentially better than the previous one. Moreover, these hopsets are also significantly sparser than their counterparts from [11]. We apply these hopsets to achieve the following online variant of shortest paths in the PRAM model: preprocess a given weighted graph within polylogarithmic time, and then given any query vertex v, report all approximate shortest paths from v in constant time. All previous constructions of hopsets require either polylogarithmic time per query or polynomial preprocessing time.

Miller et al. [48] devised a distributed 1 algorithm in the CONGEST model that, given a parameter k = 1,2,…, constructs an O ( k )-spanner of an input unweighted n -vertex graph with O ( n 1+1/ k ) expected edges in O ( k ) rounds of communication. In this article, we improve the result of Reference [48] by showing a k -round distributed algorithm in the same model that constructs a (2 k −1)-spanner with O ( n 1+1/ k }/ϵ) edges, with probability 1−ϵ for any ϵ>0. Moreover, when k =ω(log n ), our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n (1+ o (1)), with probability 1− o (1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that are sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large k , it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for (1+ϵ, β)-spanners and emulators. In particular, we show that for any unweighted n -vertex graph and any ϵ > 0, there exists a (1+ ϵ, (log log n / ϵ) log log n )-emulator with O ( n ) edges. All previous constructions of (1+ϵ, β)-spanners and emulators employ a superlinear number of edges for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths’ computation in unweighted graphs.

Distributed \em routing is one of the most central and fundamental problems in the area of Distributed Graph Algorithms. It was extensively studied for almost thirty years. Nevertheless, the currently existing solutions for this problem require either prohibitively large construction (aka preprocessing) time, or prohibitively large memory usage either during the construction or during the routing phase, and suffer from suboptimal labels and tables' sizes. We devise a distributed routing scheme that enjoys the best of all worlds. Specifically, its construction time and memory requirements during the construction phase are near-optimal, and so is also the tradeoff between the sizes of routing tables and labels on the one hand, and the stretch on the other. On the way to this result, we also improve upon existing solutions for the distributed exact \em tree routing problem. Previous solutions require Ω(√ ) memory, and provide tables and labels of size O(log n) and O(log^2 n), respectively. Our solution, on the other hand, requires just O(log n) memory, and has tables of size O(1), and labels of size O(log n). These bounds match the bounds of the best-known centralized solution.

The metric Ramsey problem asks for the largest subset S of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor [MN07] devised the so called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems. In this paper we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of Ramsey Spanning Trees. We ask for the largest subset S ⊆ V of a given graph G = (V, E), such that there exists a spanning tree of G that has small stretch for S. Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to all other vertices. The union of these trees serves as a special type of spanner, a tree-padding spanner. We use this spanner to devise the first compact stateless routing scheme with O(1) routing decision time, and labels which are much shorter than in all currently existing schemes. We first revisit the metric Ramsey problem, and provide a new deterministic construction. We prove that for every k, any n-point metric space has a subset S of size at least n1–1/k which embeds into an ultrametric with distortion 8k. We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. Building on this result, we prove that for every k, any n-vertex graph G = (V, E) has a subset S of size at least n1–1/k, and a spanning tree of G, that has stretch O(k log log n) between any point in S and any point in V.

Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been successfully applied for approximation algorithms [N. Linial, E. London, and Y. Rabinovich, Combinatorica, 15 (1995), pp. 215--245], online algorithms [N. Bansal et al., Proceedings of the 52th Annual IEEE Symposium on Foundations of Computer Science, FOCS '08, IEEE Computer Society, Washington, DC, 2011, pp. 267--276], distributed algorithms [M. Khan et al., Distrib. Comput., 25 (2012), pp. 189--205], and for computing sparsifiers [Y. Shavitt and T. Tankel, IEEE/ACM Trans. Netw., 12 (2004), pp. 993--1006]. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices/points should enjoy a better service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee. In this paper we alleviate this limitation by devising a suite of prioritized metric data structures and embeddings. We show that given a priority ranking $(x_1,x_2,\ldots,x_n)$ of the graph vertices (resp., metric points) one can devise a metric data structure (resp., embedding) in which the stretch (resp., distortion) incurred by any pair containing a vertex $x_j$ will depend on the rank $j$ of the vertex. We also show that other important parameters, such as the label size and (in some sense) the dimension, may depend only on $j$. In some of our metric data structures (resp., embeddings) we achieve both prioritized stretch (resp., distortion) and label size (resp., dimension) simultaneously. The worst-case performance of our metric data structures and embeddings is typically asymptotically no worse than of their nonprioritized counterparts.

In the distributed message-passing setting a communication network is represented by a graph whose vertices represent processors that perform local computations and communicate over the edges of the graph. In the distributed edge-coloring problem the processors are required to assign colors to edges, such that all edges incident on the same vertex are assigned distinct colors. The previously-known deterministic algorithms for edge-coloring employed at least (2Δ - 1) colors, even though any graph admits an edge-coloring with Δ + 1 colors [36]. Moreover, the previously-known deterministic algorithms that employed at most O(Δ) colors required superlogarithmic time [3,6,7,17]. In the current paper we devise deterministic edge-coloring algorithms that employ only Δ + o(Δ) colors, for a very wide family of graphs. Specifically, as long as the arboricity a of the graph is a = O(Δ1 - ε), for a constant ε > 0, our algorithm computes such a coloring within polylogarithmic deterministic time. We also devise significantly improved deterministic edge-coloring algorithms for general graphs for a very wide range of parameters. Specifically, for any value κ in the range [4Δ, 2o(log Δ) ⋅ Δ], our κ-edge-coloring algorithm has smaller running time than the best previously-known κ-edge-coloring algorithms. Our algorithms are actually much more general, since edge-coloring is equivalent to vertex-coloring of line graphs. Our method is applicable to vertex-coloring of the family of graphs with bounded diversity that contains line graphs, line graphs of hypergraphs, and many other graphs. We significantly improve upon previous vertex-coloring of such graphs, and as an implication also obtain the improved edge-coloring algorithms for general graphs.

Distributed minimum spanning tree (MST) problem is one of the most central and fundamental problems in distributed graph algorithms. Kutten and Peleg [KP98] devised an algorithm with running time O(D + √n . log* n), where D is the hop-diameter of the input n-vertex m-edge graph, and with message complexity O(m + n3/2). Peleg and Rubinovich [PR99] showed that the running time of the algorithm of [KP98] is essentially tight, and asked if one can achieve near-optimal running time together with near-optimal message complexity.

Miller et al. [43] devised a distributed1 algorithm in the CONGEST model, that given a parameter k = 1, 2,…, constructs an O(k)-spanner of an input unweighted n-vertex graph with O(n1+1/k) expected edges in O(k) rounds of communication. In this paper we improve the result of [43], by showing a k-round distributed algorithm in the same model, that constructs a (2k — 1)- spanner with O(n1+1/k/∊) edges, with probability 1 — ∊, for any ∊ > 0. Moreover, when k = ω(log n), our algorithm produces (still in k rounds) ultra-sparse spanners, i.e., spanners of size n(1 + o(1)), with probability 1 — o(1). To our knowledge, this is the first distributed algorithm in the CONGEST or in the PRAM models that constructs spanners or skeletons (i.e., connected spanning subgraphs) that sparse. Our algorithm can also be implemented in linear time in the standard centralized model, and for large k, it provides spanners that are sparser than any other spanner given by a known (near-)linear time algorithm. We also devise improved bounds (and algorithms realizing these bounds) for (1 + ∊, ß)-spanners and emulators. In particular, we show that for any unweighted n-vertex graph and any ∊ > 0, there exists a with O(n) edges. All previous constructions of (1 + ∊, β)-spanners and emulators employ a superlinear number of edges, for all choices of parameters. Finally, we provide some applications of our results to approximate shortest paths’ computation in unweighted graphs.

The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in O(n) time, where n is the number of vertices in the input graph G. Peleg and Rubinovich, FOCS'99, showed a lower bound of Ω(D + √n) for this problem, where D is the hop-diameter of G.

In this paper we study terminal embeddings , in which one is given a finite metric ( X , d X ) (or a graph G = ( V , E ) ) and a subset K ⊆ X of its points are designated as terminals . The objective is to embed the metric into a normed space, while approximately preserving all distances among pairs that contain a terminal. We devise such embeddings in various settings, and conclude that even though we have to preserve ≈ | K | ⋅ | X | pairs, the distortion depends only on | K | , rather than on | X | . We also strengthen this notion, and consider embeddings that approximately preserve the distances between all pairs, but provide improved distortion for pairs containing a terminal. Surprisingly, we show that such embeddings exist in many settings, and have optimal distortion bounds both with respect to X × X and with respect to K × X . Moreover, our embeddings have implications to the areas of Approximation and Online Algorithms. In particular, [10] devised an O ˜ ( log ⁡ r ) -approximation algorithm for sparsest-cut instances with r demands. Building on their framework, we provide an O ˜ ( log ⁡ | K | ) - approximation for sparsest-cut instances in which each demand is incident on one of the vertices of K (aka, terminals). Since | K | ≤ r , our bound generalizes that of [10] .

A $(\beta,\epsilon)$-hopset for a weighted undirected n-vertex graph $G=(V,E)$ is a set of edges, whose addition to the graph guarantees that every pair of vertices has a path between them that contains at most $\beta$ edges, whose length is within $1+\epsilon$ of the shortest path. In her seminal paper, Cohen [ J. ACM, 47 (2000), pp. 132--166] introduced the notion of hopsets in the context of parallel computation of approximate shortest paths, and since then it has found numerous applications in various settings, such as dynamic graph algorithms, distributed computing, and the streaming model. Cohen [ J. ACM, 47 (2000), pp. 132--166] devised efficient algorithms for constructing hopsets with polylogarithmic in n number of hops. Her constructions remain the state of the art since the publication of her paper in the proceedings of STOC'94, i.e., for more than two decades. In this paper we exhibit the first construction of sparse hopsets with a constant number of hops. We also find efficient algorithms for hopsets in various computational settings, improving the best-known constructions. Generally, our hopsets strictly outperform the hopsets of [ J. ACM, 47 (2000), pp. 132--166] in terms of both their parameters and the resources required to construct them. We demonstrate the applicability of our results for the fundamental problem of computing approximate shortest paths from $s$ sources. Our results improve the running time for this problem in the parallel, distributed, and streaming models for a vast range of s.

For a pair of positive parameters D,Χ, a partition P of the vertex set V of an n-vertex graph G = (V,E) into disjoint clusters of diameter at most D each is called a (D,Χ) network decomposition}, if the supergraph G(P), obtained by contracting each of the clusters of P, can be properly Χ-colored. The decomposition P is said to be strong (resp., weak) if each of the clusters has strong (resp., weak) diameter at most D, i.e., if for every cluster C ∈ P and every two vertices u,v ∈ C, the distance between them in the induced graph G(C) of C (resp., in G) is at most D.

Given a distributed network represented by a weighted undirected graph G=(V,E) on n vertices, and a parameter k, we devise a distributed algorithm that computes a routing scheme in O(n1/2+1/k+D)⋅ no(1) rounds, where D is the hop-diameter of the network. The running time nearly matches the lower bound of Ω(n1/2+D) rounds (which holds for any scheme with polynomial stretch). The routing tables are of size Õ(n1/k), the labels are of size O(k log2n), and every packet is routed on a path suffering stretch at most 4k-5+o(1). Our construction nearly matches the state-of-the-art for routing schemes built in a centralized sequential manner. The previous best algorithms for building routing tables in a distributed small messages model were by [LP13a, STOC 2013] and [LP15, PODC 2015]. The former has similar properties but suffers from substantially larger routing tables of size O(n1/2+1/k), while the latter has sub-optimal running time of Õ(min{(nD)1/2 ⋅ n1/k,n2/3+2/(3k)+D}).

Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following: —An MIS algorithm running in O (log 2 Δ + 2 o (√log log n ) ) time, where Δ is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when log n ≪ Δ ≪ 2√log n , and comes close to the Ω(log Δ / log log Δ lower bound of Kuhn, Moscibroda, and Wattenhofer. —A maximal matching algorithm running in O (log Δ + log 4 log n ) time. This is the first significant improvement to the 1986 algorithm of Israeli and Itai. Moreover, its dependence on Δ is nearly optimal . —A (Δ + 1)-coloring algorithm requiring O (log Δ + 2 o (√log log n ) time, improving on an O (log Δ + √log n )-time algorithm of Schneider and Wattenhofer. —A method for reducing symmetry-breaking problems in low arboricity/degeneracy graphs to low-degree graphs. (Roughly speaking, the arboricity or degeneracy of a graph bounds the density of any subgraph.) Corollaries of this reduction include an O (√log n )-time maximal matching algorithm for graphs with arboricity up to 2√log n and an O (log 2/3 n )-time MIS algorithm for graphs with arboricity up to 2 (log n )1/3 . Each of our algorithms is based on a simple but powerful technique for reducing a randomized symmetry-breaking task to a corresponding deterministic one on a poly(log n )-size graph.

Thorup and Zwick [2001a] proposed a landmark distance oracle with the following properties. Given an n -vertex undirected graph G = ( V , E ) and a parameter k = 1, 2, …, their oracle has size O ( kn 1 + 1/ k ), and upon a query ( u , v ) it constructs a path Π between u and v of length δ( u , v ) such that d G ( u , v ) ⩽ δ( u , v ) ⩽ (2 k − 1) d G ( u , v ). The query time of the oracle from Thorup and Zwick [2001a] is O ( k ) (in addition to the length of the returned path), and it was subsequently improved to O (1) [Wulff-Nilsen 2012; Chechik 2014]. A major drawback of the oracle of Thorup and Zwick [2001a] is that its space is Ω( n · log n ). Mendel and Naor [2006] devised an oracle with space O ( n 1 + 1/ k ) and stretch O ( k ), but their oracle can only report distance estimates and not actual paths. In this article, we devise a path-reporting distance oracle with size O ( n 1 + 1/ k ), stretch O ( k ), and query time O ( n ϵ ), for an arbitrarily small constant ϵ > 0. In particular, for k = log n , our oracle provides logarithmic stretch using linear size. Another variant of our oracle has size O ( n loglog n ), polylogarithmic stretch, and query time O (loglog n ). For unweighted graphs, we devise a distance oracle with multiplicative stretch O (1), additive stretch O (β( k )), for a function β(·), space O ( n 1 + 1/ k ), and query time O ( n ϵ ), for an arbitrarily small constant ϵ > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erdős’s girth conjecture threshold (which is stretch 2 k − 1 and size O ( n 1 + 1/ k )). Breaking the girth conjecture tradeoff is achieved by exhibiting a tradeoff of different nature between additive stretch β( k ) and size O ( n 1 + 1/ k ). A similar type of tradeoff was exhibited by a construction of (1 + ϵ, β)-spanners due to Elkin and Peleg [2001]. However, so far (1 + ϵ, β)-spanners had no counterpart in the distance oracles’ world. An important novel tool that we develop on the way to these results is a distance-preserving path-reporting oracle. We believe that this oracle is of independent interest.

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].

In a seminal paper [27] for any n-vertex undirected graph G = (V,E) and a parameter k = 1, 2, …, Thorup and Zwick constructed a distance oracle of size O(kn1+1/k) which upon a query (u, v) constructs a path Π between u and ν of length δ(u, v) such that dG(u,ν) ≤ δ(u,v) ≤ (2k–1)dG(u,v). The query time of the oracle from [27] is O(k) (in addition to the length of the returned path), and it was subsequently improved to O(1) [29, 11]. A major drawback of the oracle of [27] is that its space is Ω(n · log n). Mendel and Naor [18] devised an oracle with space O(n1+1/k) and stretch O(k), but their oracle can only report distance estimates and not actual paths. In this paper we devise a path-reporting distance oracle with size O(n1+1/k), stretch O(k) and query time O(nε), for an arbitrarily small ε > 0. In particular, for k = log n our oracle provides logarithmic stretch using linear size. Another variant of our oracle has linear size, polylogarithmic stretch, and query time O (log log n). For unweighted graphs we devise a distance oracle with multiplicative stretch O(1), additive stretch O(β(k)), for a function β, space O(n1+1/k · β), and query time O(nε), for an arbitrarily small constant ε > 0. The tradeoff between multiplicative stretch and size in these oracles is far below Erdös's girth conjecture threshold (which is stretch 2k — 1 and size O(n)1+1/k)). Breaking the girth conjecture tradeoff is achieved by exhibiting a tradeoff of different nature between additive stretch β(k) and size O(n1+1/k). A similar type of tradeoff was exhibited by a construction of (1 + ε, β)-spanners due to Elkin and Peleg [16]. However, so far (1 + ε, β)-spanners had no counterpart in the distance oracles' world. An important novel tool that we develop on the way to these results is a distance-preserving path-reporting oracle. We believe that this oracle is of independent interest.

Graph coloring is a central problem in distributed computing. Both vertex- and edge-coloring problems have been extensively studied in this context. In this paper we show that a (2Δ — l)-edge-coloring can be computed in time smaller than logε n for any ε > 0, specifically, in rounds. This establishes a separation between the (2Δ — 1)-edge-coloring and Maximal Matching problems, as the latter is known to require time [15]. No such separation is currently known between the (Δ + l)-vertex-coloring and Maximal Independent Set problems. We devise a (1 + ε)Δ-edge-coloring algorithm for an arbitrarily small constant ε > 0. This result applies whenever Δ ≥ Δε, for some constant Δε which depends on e. The running time of this algorithm is . A much earlier logarithmic-time algorithm by Dubhashi, Grable and Panconesi [11] assumed Δ ≥ (log n)1+Ω(1). For Δ = (log n)1+Ω(1) the running time of our algorithm is only O (log* n). This constitutes a drastic improvement of the previous logarithmic bound [11, 9]. Our results for (2Δ — 1)-edge-coloring also follows from our more general results concerning (1 — ε)-locally sparse graphs. Specifically, we devise a (Δ + l)-vertex coloring algorithm for (1 — ε)-locally sparse graphs that runs in O(log* Δ + log(l/ε)) rounds for any ε > 0, provided that ε Δ = (log n)1+Ω(1). We conclude that the (Δ + l)-vertex coloring problem for (1 — ε)-locally sparse graphs can be solved in time. This imply our result about (2Δ — 1)-edge-coloring, because (2Δ — 1)-edge-coloring reduces to (Δ + l)-vertex-coloring of the line graph of the original graph, and because line graphs are (1/2 + o(1))-locally sparse.

Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic methodology, which has been successfully applied for approximation algorithms [21], online algorithms [7], distributed algorithms [19] and for computing sparsifiers [28]. However, this methodology appears to have a limitation: the worst-case performance inherently depends on the cardinality of the metric, and one could not specify in advance which vertices/points should enjoy a better service (i.e., stretch/distortion, label size/dimension) than that given by the worst-case guarantee.

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.

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)$.

The focus of this paper is on quantum distributed computation, where we investigate whether quantum communication can help in speeding up distributed network algorithms. Our main result is that for certain fundamental network problems such as minimum spanning tree, minimum cut, and shortest paths, quantum communication does not help in substantially speeding up distributed algorithms for these problems compared to the classical setting.

The distributed $(\Delta + 1)$-coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of gradually improving algorithms has been published. The state-of-the-art running time, prior to our work, is $O(\Delta \log \Delta + \log^* n)$, due to Kuhn and Wattenhofer [Proceedings of the $25$th Annual ACM Symposium on Principles of Distributed Computing, Denver, CO, 2006, pp. 7--15]. Linial [Proceedings of the $28$th Annual IEEE Symposium on Foundation of Computer Science, Los Angeles, CA, 1987, pp. 331--335] proved a lower bound of $\frac{1}{2} \log^* n$ for the problem, and Szegedy and Vishwanathan [Proceedings of the 25th Annual ACM Symposium on Theory of Computing, San Diego, CA, 1993, pp. 201--207] provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve a running time smaller than $\Theta(\Delta \log \Delta)$. We present a deterministic $(\Delta + 1)$-coloring distributed algorithm with running time $O(\Delta) + \frac{1}{2} \log^* n$. We also present a trade-off between the running time and the number of colors, and devise an $O(\lambda\cdot\Delta)$-coloring algorithm, with running time $O(\Delta / \lambda + \log^* n)$, for any parameter $\lambda > 1$. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan and achieves running time which is linear in the maximum degree $\Delta$. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm does not belong to the family of locally iterative algorithms. On the way to this result we study a generalization of the notion of graph coloring, which is called defective coloring [L. Cowen, R. Cowen, and D. Woodall, J. Graph Theory, 10 (1986), pp. 187--195]. In an $m$-defective $p$-coloring the vertices are colored with $p$ colors so that each vertex has up to $m$ neighbors with the same color. We show that an $m$-defective $p$-coloring with reasonably small $m$ and $p$ can be computed very efficiently in the distributed setting. We also develop a technique to employ multiple defective colorings of various subgraphs of the original graph $G$ for computing a $(\Delta+1)$-coloring of $G$. We believe that these techniques are of independent interest.

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.

We present new bounds on the locality of several classical symmetry breaking tasks in distributed networks. A sampling of the results include 1) A randomized algorithm for computing a maximal matching (MM) in O(log Δ + (log log n)4) rounds, where Δ is the maximum degree. This improves a 25-year old randomized algorithm of Israeli and Itai that takes O(log n) rounds and is provably optimal for all log Δ in the range [(log log n)4, √log n]. 2) A randomized maximal independent set (MIS) algorithm requiring O(log Δ√log n) rounds, for all Δ, and only 2O(√log log n) rounds when Δ = poly(log n). These improve on the 25-year old O(log n)-round randomized MIS algorithms of Luby and Alon, Babai, and Itai when log Δ ≫ √log n. 3) A randomized (Δ + 1)-coloring algorithm requiring O(log Δ + 2O((√log log n)) rounds, improving on an algorithm of Schneider and Wattenhofer that takes O(log Δ + √log n) rounds. This result implies that an O(Δ)-coloring can be computed in 2O(√log log n)rounds for all Δ, improving on Kothapalli et al.'s O(√log n)-round algorithm. We also introduce a new technique for reducing symmetry breaking problems on low arboricity graphs to low degree graphs. Corollaries of this reduction include MM and MIS algorithms for low arboricity graphs (e.g., planar graphs and graphs that exclude any fixed minor) requiring O(√log n) and O(log2/3n) rounds w.h.p., respectively.

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.

We study the edge-coloring problem in the message-passing model of distributed computing. This is one of the most fundamental problems in this area. Currently, the best-known deterministic algorithms for (2Δ-1)-edge-coloring requires O(Δ) + log* n time [23], where Δ is the maximum degree of the input graph. Also, recent results of [5] for vertex-coloring imply that one can get an O(Δ)-edge-coloring in O(Δµ" log n) time, and an O(Δ1 + µ)-edge-coloring in O(log Δ log n) time, for an arbitrarily small constant µ > 0.

Consider an n -vertex graph G = ( V , E ) of maximum degree Δ , and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G . The communication is synchronous, that is, it proceeds in discrete rounds. In the distributed vertex coloring problem, the objective is to color G with Δ + 1, or slightly more than Δ + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as running time .) Efficient randomized algorithms for this problem are known for more than twenty years [Alon et al. 1986; Luby 1986]. Specifically, these algorithms produce a ( Δ + 1)-coloring within O (log n ) time, with high probability. On the other hand, the best known deterministic algorithm that requires polylogarithmic time employs O ( Δ 2 ) colors. This algorithm was devised in a seminal FOCS’87 paper by Linial [1987]. Its running time is O (log * n ). In the same article, Linial asked whether one can color with significantly less than Δ 2 colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area. In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs Δ 1+ o (1) colors, and runs in polylogarithmic time. Specifically, the running time of our algorithm is O ( f ( Δ )log Δ log n ), for an arbitrarily slow-growing function f ( Δ ) = ω (1). We can also produce an O ( Δ 1+ η )-coloring in O (log Δ log n )-time, for an arbitrarily small constant η > 0, and an O ( Δ )-coloring in O ( Δϵ log n ) time, for an arbitrarily small constant ϵ > 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity a , our algorithm produces an O ( a 1+ η )-coloring, for an arbitrarily small constant η > 0, in time O (log a log n ).

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 present a streaming algorithm for constructing sparse spanners and show that our algorithm significantly outperforms the state-of-the-art algorithm for this task (due to Feigenbaum et al.). Specifically, the processing time per edge of our algorithm is O (1), and it is drastically smaller than that of the algorithm of Feigenbaum et al., and all other efficiency parameters of our algorithm are no greater (and some of them are strictly smaller) than the respective parameters of the state-of-the-art algorithm. We also devise a fully dynamic centralized algorithm maintaining sparse spanners. This algorithm has incremental update time of O (1), and a nontrivial decremental update time. To our knowledge, this is the first fully dynamic centralized algorithm for maintaining sparse spanners that provides nontrivial bounds on both incremental and decremental update time for a wide range of stretch parameter t .

Consider an n-vertex graph G = (V,E) of maximum degree Δ, and suppose that each vertex v ∈ V hosts a processor. The processors are allowed to communicate only with their neighbors in G. The communication is synchronous, i.e., it proceeds in discrete rounds.

The problem of constructing dense subsets S of {1, 2, …, n} that contain no three-term arithmetic progression was introduced by Erdős and Turán in 1936. They have presented a construction with elements. Their construction was improved by Salem and Spencer, and further improved by Behrend in 1946. The lower bound of Behrend is Since then the problem became one of the most central, most fundamental, and most intensively studied problems in additive number theory. Nevertheless, no improvement of the lower bound of Behrend has been reported since 1946. In this paper we present a construction that improves the result of Behrend by a factor of , and shows that In particular, our result implies that the construction of Behrend is not optimal. Our construction and proof are elementary and self-contained. Also, the construction can be implemented by an efficient algorithm. Behrend's construction has numerous applications in Theoretical Computer Science. In particular, it is used for fast matrix multiplication, for property testing, and in the area of communication complexity. Plugging in our construction instead of Behrend's construction in the matrix multiplication algorithm of Coppersmith and Winograd improves the state-of-the-art upper bound on the complexity of the matrix multiplication by a factor of logv n, for some fixed constant ν > 0. We also present an application of our technique in Computational Geometry.

The distributed ( ∆ + 1)-coloring problem is one of most fundamental and well-studied problems of Distributed Algorithms. Starting with the work of Cole and Vishkin in 86, there was a long line of gradually improving algorithms published. The current state-of-the-art running time is O(∆log ∆ + log ∗ n), due to Kuhn and Wattenhofer, PODC’06. Linial (FOCS’87) has proved a lower bound of 1 2 log ∗ n for the problem, and Szegedy and Vishwanathan (STOC’93) provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve running time smaller than Θ(∆log ∆). We present a deterministic (∆+1)-coloring distributed algorithm with running time O(∆)+ 1 2 log ∗ n. We also present a tradeoff between the running time and the number of colors, and devise an O( ∆ 1+ǫ)-coloring algorithm with running time O( ∆ 1−ǫ +log ∗ n), for any constant ǫ, 0 < ǫ ≤ 1/4. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan, and achieves running time which is linear in the maximum degree ∆. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm is not from the family of locally iterative algorithms. On the way to this result we introduce a generalization of the notion of graph coloring, which we call relaxed coloring. In an m-relaxed p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-relaxed p-coloring with reasonably small m and p can be computed very efficiently. We also develop a technique to employ multiple relaxed colorings of various subgraphs of the original graph G for computing a ( ∆ + 1)-coloring of G. We believe that these techniques and the notion of relaxed coloring are of independent interest.

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.

We study the distributed maximal independent set (henceforth, MIS) problem on sparse graphs. Currently, there are known algorithms with a sublogarithmic running time for this problem on oriented trees and graphs of bounded degrees. We devise the first sublogarithmic algorithm for computing MIS on graphs of bounded arboricity. This is a large family of graphs that includes graphs of bounded degree, planar graphs, graphs of bounded genus, graphs of bounded treewidth, graphs that exclude a fixed minor, and many other graphs. We also devise efficient algorithms for coloring graphs from these families. These results are achieved by the following technique that may be of independent interest. Our algorithm starts with computing a certain graph-theoretic structure, called Nash-Williams forests-decomposition. Then this structure is used to compute the MIS or coloring. Our results demonstrate that this methodology is very powerful. Finally, we show nearly-tight lower bounds on the running time of any distributed algorithm for computing a forests-decomposition.

We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch $O (\log^{2} n \log \log n)$. Moreover, we show that this tree can be constructed in time $O (m \log n + n \log^2 n)$ in general, and in time $O (m \log n)$ if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique. Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from $ m 2^{(O (\sqrt{\log n\log\log n})) }$ to $m \log^{O (1)}n$, and to $O ( n \log^{2} n \log \log n)$ when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.

Currently, there are no known explicit algorithms for the great majority of graph problems in the dynamic distributed message-passing model. Instead, most state-of-the-art dynamic distributed algorithms are constructed by composing a static algorithm for the problem at hand with a simulation technique that converts static algorithms to dynamic ones. We argue that this powerful methodology does not provide satisfactory solutions for many important dynamic distributed problems, and this necessitates developing algorithms for these problems from scratch.

We show that for every radio network G = (V, E) and source s ∈ V, there exists a radio broadcast schedule for G of length Rad(G, s) + O(√Rad(G, s) ⋅log2 n) = O(Rad(G, s) + log4 n), where Rad(G, s) is the radius of the radio network G with respect to the source s. This result improves the previously best-known upper bound of O(Rad(G, s) + log5 n) due to Gaber and Mansour [1995].

The design of distributed approximation protocols is a relatively new and rapidly developing area of research. However, so far, little progress has been made in the study of the hardness of distributed approximation. In this paper we initiate the systematic study of this subject and show strong unconditional lower bounds on the time-approximation trade-off of the distributed minimum spanning tree problem, and show some of its variants.

We introduce and study the notions of pairwise and sourcewise preservers. Given an undirected N-vertex graph G = (V,E) and a set P of pairs of vertices, let G' = (V,H), H \subseteq E, be called a pairwise preserver of G with respect to P if for every pair {u,w} \in P, distG'(u,w) = distG(u,w). For a set S \subseteq V of sources, a pairwise preserver of G with respect to the set of all pairs P = (S \atop 2) of sources is called a sourcewise preserver of G with respect to S . We prove that for every undirected possibly weighted N-vertex graph G and every set P of P = O(N1/2) pairs of vertices of G, there exists a linear-size pairwise preserver of G with respect to P. Consequently, for every subset S \subseteq V of S = O(N1/4) sources, there exists a linear-size sourcewise preserver of G with respect to S. On the negative side we show that neither of the two exponents (1/2 and 1/4) can be improved even when the attention is restricted to unweighted graphs. Our lower bounds involve constructions of dense convexly independent sets of vectors with small Euclidean norms. We believe that the link between the areas of discrete geometry and spanners that we establish is of independent interest and might be useful in the study of other problems in the area of low-distortion embeddings.

We show that every weighted connected graph G contains as a subgraph a spanning tree into which the edges of G can be embedded with average stretch O (log2 n log log n). Moreover, we show that this tree can be constructed in time O (m log2n) in general, and in time O (mlog n) if the input graph is unweighted. The main ingredient in our construction is a novel graph decomposition technique.Our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of Spielman and Teng from m2(O√lognlog log n) to m log O(1)n and to O (n log2n log log n) when the system is planar. Our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.

Consider a synchronous network of processors, modeled by directed or undirected graph $G = (V,E)$, in which in each round every processor is allowed to choose one of its neighbors and to send a message to this neighbor. Given a processor $s \in V$ and a subset $T \subseteq V$ of processors, the telephone multicast problem requires computing the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of T. The particular case $T = V$ is called the telephone broadcast problem. These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the undirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the directed variants of these problems is an open problem, posed by Ravi in [Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, (FOCS '94), 1994, pp. 202-213]. We devise a combinatorial logarithmic approximation algorithm for these problems that applies also for the directed broadcast problem. Our algorithm has significantly smaller running time and seems to reveal more information about the combinatorial structure of the solution than the previous algorithms that are based on linear programming. We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the undirected (resp., directed) broadcast problem we show that it is NP-hard (resp., impossible unless $NP \subseteq DTIME(n^{O(\log n)})$) to approximate it within a ratio of $3 - \epsilon$ for any $\epsilon > 0$ (resp., $\Omega(\sqrt{\log n})$).

For an unweighted graph $G = (V,E)$, $G' = (V,E')$ is a subgraph if $E' \subseteq E$, and $G' = (V',E',\omega)$ is a Steiner graph if $V \subseteq V'$, and for any pair of vertices $u,w \in V$, the distance between them in $G'$ (denoted $d_{G'}(u,w)$) is at least the distance between them in G (denoted $d_G(u,w)$). In this paper we introduce the notion of distance preserver. A subgraph (resp., Steiner graph) $G'$ of a graph G is a subgraph (resp., Steiner) D-preserver of G if for every pair of vertices $u,w \in V$ with $d_G(u,w) \ge D$, $d_{G'}(u,w) = d_G(u,w)$. We show that any graph (resp., digraph) has a subgraph D-preserver with at most $O(n^2/D)$ edges (resp., arcs), and there are graphs and digraphs for which any undirected Steiner D-preserver contains $\Omega(n^2/D)$ edges. However, we show that if one allows a directed Steiner (diSteiner) D-preserver, then these bounds can be improved. Specifically, we show that for any graph or digraph there exists a diSteiner D-preserver with $O({{n^2 \cdot \log D} \over {D \cdot \log n}})$ arcs, and that this result is tight up to a constant factor. We also study D-preserving distance labeling schemes, that are labeling schemes that guarantee precise calculation of distances between pairs of vertices that are at a distance of at least D one from another. We show that there exists a D-preserving labeling scheme with labels of size $O({{n} \over {D}} \log^2 n)$, and that labels of size $\Omega({{n} \over {D}} \log D)$ are required for any D-preserving labeling scheme.

The input for the radio broadcast problem is an undirected n-vertex graph G and a source node s. The goal is to send a message from s to the rest of the vertices in the minimum number of rounds. In a round, a vertex receives the message only if exactly one of its neighbors transmits. The radio broadcast problem admits an $O(\log^2 n)$ approximation [CW-87,KP-04]. [I. Chlamtac and O. Weinstein, in Proceedings of the IEEE INFOCOM, 1987, pp. 874-881; D. Kowalski and A. Pelc, in APPROX-RANDOM, Lecture Notes in Comput. Sci. 3122, Springer, Berlin, 2004, pp. 171-182]. In this paper we consider the additive approximation ratio of the problem. We prove that there exists a constant c so that the problem cannot be approximated within an additive term of $c\log^2 n$, unless $NP\subseteq BTIME(n^{O(\log\log n)})$.

We study the s-sources almost shortest paths (abbreviated s-ASP) problem. Given an unweighted graph G = (V,E), and a subset S ⊆ V of s nodes, the goal is to compute almost shortest paths between all the pairs of nodes S × V. We devise an algorithm with running time O(∣E∣nρ + s · n1 + ζ) for this problem that computes the paths Pu,w for all pairs (u,w) ∈ S × V such that the length of Pu,w is at most (1 + ε) dG(u,w) + β(ζ,ρ,ε), and β(ζ,ρ,ε) is constant when ζ, ρ, and ε are arbitrarily small constants. We also devise a distributed protocol for the s-ASP problem that computes the paths Pu,w as above, and has time and communication complexities of O(s · Diam(G) + n1 + ζ/2) (respectively, O(s · Diam(G) log3 n + n1 + ζ/2 log n)) and O(∣E∣ nρ + s · n1 + ζ) (respectively, O(∣E∣ nρ + s · n1 + ζ + n1 + ρ + ζ(ρ − ζ/2)/2)) in the synchronous (respectively asynchronous) setting. Our sequential algorithm, as well as the distributed protocol, is based on a novel algorithm for constructing (1 + ε, β(ζ,ρ, ε))-spanners of size O(n1 + ζ), developed in this article. This algorithm has running time of O(∣E∣ nρ), which is significantly faster than the previously known algorithm given in Elkin and Peleg [2001], whose running time is Õ(n2 + ρ). We also develop the first distributed protocol for constructing (1 + ε,β)-spanners. The communication complexity of this protocol is near optimal.

For an unweighted undirected graph G= (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G'= (V,H), H ⊆ E, is called an (α,β)-spanner of G if for every pair of vertices u, v ∈ V, distG'(u,v) ≤ α • distG'(u,v) + β.It was shown in [20] that for any e > 0, κ = 1,2, ..., there exists an integer β = β(e,κ) such that for every n-vertex graph G there exists a (1+e,β)-spanner G' with O(n1+1/κ) edges. An efficient distributed protocol for constructing (1+e,β)-spanners was devised in [18]. The running time and the communication complexity of that protocol are O(n1+ρ) and O(|E|nρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β.In this paper we devise a protocol with a drastically improved running time (O(nρ) as opposed to (O(n1+ρ) for constructing (1+e,β)-spanners. Our protocol has the same communication complexity as the protocol of [18], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [18].We also show that our protocol for constructing (1+e, β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n1+1/κ • log n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1 + e) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(nρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [21] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n1+1/κ) time for processing each edge of the input graph. However, the algorithm of [21] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space.

The design of distributed approximation protocols is a relatively new rapidly developing area of research. However, so far little progress was done in the study of the hardness of distributed approximation. In this paper we initiate the systematic study of this subject, and show strong unconditional lower bounds on the time-approximation tradeoff of the distributed minimum spanning tree problem, and some of its variants.

An {\em $(\alpha,\beta)$-spanner} of a graph G is a subgraph H such that $\mathit{dist}_H(u,w)\le \alpha\cdot \mathit{dist}t_G(u,w)+\beta$ for every pair of vertices u,w, where dist G' (u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible $(2\kappa-1,0)$-spanner (also known as multiplicative $(2\kappa-1)$-spanner) of size $O(n^{1+1/\kappa})$ for every integer $\kappa\ge 1$, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size ${\tilde O}(n^{3/2})$. This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant $\epsilon, \lambda > 0$ there exists a constant $\beta = \beta(\epsilon, \lambda)$ such that for every n-vertex graph G there is an efficiently constructible $(1+ \epsilon, \beta)$-spanner of size $O(n^{1 + \lambda})$.

(MATH) Consider a synchronous network of processors, modeled by directed or undirected graph G = (V,E), in which on each round every processor is allowed to choose one of its neighbors and to send him a message. Given a processor s ε V, and a subset T ⊆ V of processors, the telephone multicast problem requires to compute the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of T. The particular case T = V is called telephone broadcast problem.These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the undirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the directed variants of these problems is anopen problem, posed in [15].We devise a combinatorial logarithmic approximation algorithm for these problems, that applies also for the directed broadcast problem. Our algorithm has significantly smaller running time, and seems to reveal more information about the combinatorial structure of the solution, than the previous algorithms, that are based on linear programming.(MATH) We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the undirected (resp., directed) broadcast problem we show that it is NP-hard (resp., impossible unless $NP ⊇ DTIME(nO(log n))) to approximate it within a ratio of 3 —ε for any ε ρ 0 (resp., ω(\sqrt log n)).Finally, we study the radio broadcast problem. Its setting is similar to the telephone broadcast problem, but in every round every processor may either send a message to all its neighbors or may not send it at all. A processor is informed in a certain round if and only if it receives a message from precisely one neighbor.(MATH) This problem was known to admit O(log2 n)-approximation algorithm, but no hardness of approximation was known. In this paper we show that the problem is ω(log n)-inapproximable unless NP ⊆ BPTIME(nlog log n}).

We study the s-sources almost shortest paths (shortly, s-ASP) problem. Given an unweighted graph G = (V, E), and a subset S n V of s nodes, the goal is to compute almost shortest paths between all the pairs of nodes S x V. We devise an algorithm with running time O(¦E¦ nr + s · n1+z) for this problem that computes the paths Pu, w for all pairs (u, w) ∈ S x V such that the length of Pu, w is at most (1 + ∈) dG (u, w) + b(z, r, ∈), and b(z, r, ∈) is constant when z, r and ∈ are (one can choose arbitrarily small constants z, r and ∈).We also devise a distributed protocol for the s-ASP problem that computes the paths Pu, w as above, and has time and communication complexities of O(s · Diam(G) + n1+z/2) (resp., O(s · Diam(G) log3n + n1+z/2 log n)) and O(¦E¦ nr + s · n1+z (resp., O(¦E¦nrgr; + s · n1+z + n1+r+z(r-z/2)/2)) in the synchronous (resp., asynchronous) setting.Our sequential algorithm, as well as the distributed protocol, is based on a novel algorithm for constructing (1 + ∈, b(z, r, ∈))-spanners of size O(n1+5), developed in this paper. This algorithm has running time of O(¦E¦ nr), which is significantly faster than the previously known algorithm of [20], whose running time is O(n2+r). We also develop the first distributed protocol for constructing (1 + ∈, b)-spanners. The time and communication complexities of this protocol are near-optimal.

An (α,Β)-spanner of a graph G is a subgraph H such that d_H(u,w)\le α\cdot d_G(u,w)+Β for every pair of vertices u,w, where d_{G'}(u,w) denotes the distance between two vertices u and v in G'. It is known that every graph G has a polynomially constructible (2κ-1,0)-spanner (a.k.a. multiplicative (2κ-1)-spanner) of size O(n^{1+1/κ}) for every integer κ\ge 1, and a polynomially constructible (1,2)-spanner (a.k.a. additive 2-spanner) of size \tO(n^{3/2}). This paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to O(n), at the cost of allowing the additive term to be a sufficiently large constant. More formally, we show that for any constant ε, δ > 0 there exists a constant Β = Β(ε, δ) such that for every n-vertex graph G there is an efficiently constructible (1+ ε, Β)-spanner of size O(n^{1 + δ}). It follows that for any constant ε, δ > 0 there exists a constant Β(ε, δ) such that for any n-vertex graph G = (V,E) there exists an efficiently constructible subgraph (V,H) with O(n^{1 +δ}) edges such that d_H(u,w) \le (1 + ε) d_G(u,w) for every pair of vertices.