An important tool in the design of fault-tolerant graph data structures are (L,f)-replacement path coverings (RPCs). An RPC is a family 𝒢 of subgraphs of a given graph G such that, for every set F of at most f edges, there is a subfamily 𝒢_F ⊆ 𝒢 with the following properties. 1) No subgraph in 𝒢_F contains an edge of F. 2) For each pair of vertices s,t that have a shortest path in G-F with at most L edges, one such path also exists in some subgraph in 𝒢_F. The covering value of the RPC is the total number |𝒢| of subgraphs. The query time is the time needed to compute the subfamily 𝒢_F given the set F. Weimann and Yuster [TALG'13] devised a randomized RPC with covering value Õ(fL^f) and query time Õ(f² L^f). This was derandomized by Karthik and Parter [TALG'24], who also reduced the query time to Õ(f² L). Their approach uses some heavy algebraic machinery involving error-correcting codes and an increased covering value of O((cfL log n)^{f+1}) for some constant c > 1. We instead devise a much simpler derandomization via conditional expectations that lowers the covering value back to Õ(fL^{f+o(1)}) and decreases the query time to Õ(f^{5/2} L^o(1)), assuming f = o(log L). We also investigate the optimal covering value of any (L,f)-replacement path covering (deterministic or randomized) for different parameter ranges. We provide a new randomized construction as well as improving a known lower bound, also by Karthik and Parter. For example, for f = o(log L), we give an RPC with Õ((L/f)^f L^o(1)) subgraphs and show that this is tight up to the L^o(1) term.

Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph G on n vertices and maximum degree Δ is presented as a stream of edges, and the goal is to compute a vertex coloring using a small number of colors while storing only Õ(n) bits of memory. Recent work has revealed an exponential separation between randomized and deterministic approaches in this setting: while randomized algorithms can achieve a (Δ+1)-coloring in a single pass [Assadi, Chen, and Khanna, 2019], any single-pass deterministic algorithm requires exp(Δ^Ω(1)) colors [Assadi, Chen, and Sun, 2022]. Consequently, deterministic algorithms that use few colors must necessarily make multiple passes over the stream. Prior to this work, the best known deterministic trade-offs were: an O(Δ²)-coloring in 2 passes, an O(Δ)-coloring in O(log Δ) passes [Assadi, Chen, and Sun, 2022], and a (Δ+1)-coloring in O(log Δ ⋅ log log Δ) passes [Assadi, Chakrabarti, Ghosh, and Stoeckl, 2023]. It remained open whether better trade-offs - particularly with sub-logarithmic pass complexity and linear-in-Δ palette size - were achievable. In this paper, we present a new deterministic semi-streaming algorithm that computes an O(Δ)-coloring in O(√{log Δ}) passes. This is the first deterministic streaming algorithm to achieve a coloring with palette size linear-in-Δ using sublogarithmic-in-Δ passes.

An \((\alpha,\beta)\)-spanner of an \(n\)-vertex undirected, unweighted graph \(G=(V,E)\) is a subgraph \(H\) satisfying, for all \(u,v\in V\), \(\mathrm{dist}_H(u,v)\le \alpha\cdot \mathrm{dist}_G(u,v)+\beta\). For any \(k\in\mathbb{N}\), classical results show that a \((2k-1,0)\)-spanner with \(O(n^{1+1/k})\) edges exists and is asymptotically optimal under Erdős’ girth conjecture. This conditional lower bound applies only to adjacent pairs, leaving open the possibility of improved stretch for more distant pairs.

Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains n vertices and has maximum vertex degree Δ, it is known that in the W-streaming model, an O(Δ²)-edge coloring can be computed deterministically with Õ(n) space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an O(Δ^{1.5})-edge coloring can be computed by a Õ(n)-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to Õ(Δ^{4/3+ε}) using space Õ(n) deterministically, for any constant ε > 0. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.

In this paper, we focus on two related problems, the n-Pairs Shortest Paths (n-PSP) problem and the All-Nodes Shortest Cycles (ANSC) problem. In the n-PSP problem, given a graph G with n vertices and m edges, as well as a set P ⊆ V × V consisting of at most n pairs of vertices, our objective is to estimate the distances between each pair (u,v ) in P. In the ANSC problem, the objective is to find for each node the shortest cycle that includes that particular node. In both problems, we present new algorithms and reductions that enhance the existing solutions in terms of both time complexity and approximation factor.

A distance oracle (DO) for a graph$G$is a data structure that, when queried with vertices$s,t$, returns an estimate$\widehat{d}(s,t)$of their distance in$G$. The oracle has stretch$(\alpha, \beta)$if the estimate satisfies$d(s,t)\leqslant \widehat{d}(s,t)\leqslant \alpha\cdot d(s,t)+\beta$. An$f-\mathbf{edge}$fault-tolerant distance sensitivity oracle$(f-\mathbf{DSO})$additionally receives a set$F$of up to$f$edges and estimates the distance in$G-F$. Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch$\beta > 0$allows one to make the multiplicative stretch$\alpha$arbitrarily small. This sidesteps a known lower bound of$\alpha\geqslant 3$(for$\beta=0$and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in$[0, W]$that, for any positive integer$\ell$and any$c\in(0,\ell/2]$, has stretch$(1+\frac{1}{\ell},2W)$, space$\widetilde{O}(n^{2-\frac{c}{\ell}})$, and query time$O(n^{c})$, generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an$(\alpha,\beta)- \mathbf{stretch}$DO for unweighted graphs into an$(\alpha(1+\varepsilon),\beta)-\mathbf{stretch}. f-\mathbf{DSO}$with sensitivity$f=o(\log(n)/\log\log n)$retaining sub-quadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [TheoretiCS 2024]. Combining the framework with our new DO gives an$f-\mathbf{DSO}$that, for any$\gamma\in(0, (\ell+1)/2]$, has stretch$((1+\frac{1}{\ell})(1+\varepsilon), 2)$, space$n^{2-\frac{\gamma}{(t+1)(f+1)}+o(1)}/\varepsilon^{f+2}$, and query time$\widetilde{O}(n^{\gamma}/\varepsilon^{2})$. This is the first$f-\mathbf{DSO}$with subquadratic space, near-additive stretch, and sublinear query time.

Given a simple weighted directed graph $G = (V, E, ω)$ on $n$ vertices as well as two designated terminals $s, t\in V$, our goal is to compute the shortest path from $s$ to $t$ avoiding any pair of presumably failed edges $f_1, f_2\in E$, which is a natural generalization of the classical replacement path problem which considers single edge failures only. This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where $ω\equiv 1$, the authors presented an algebraic algorithm with runtime $\tilde{O}(n^{2.9146})$, as well as a conditional lower bound of $n^{8/3-o(1)}$ against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs. As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is $\tilde{O}(n^{3-1/18})$. Besides, we also study algebraic algorithms for digraphs with small integer edge weights from $\{-M, -M+1, \cdots, M-1, M\}$. As our secondary result, we obtained a runtime of $\tilde{O}(Mn^{2.8716})$, which is faster than the previous bound of $\tilde{O}(M^{2/3}n^{2.9144} + Mn^{2.8716})$ from [Vassilevska Williams, Woldeghebriela and Xu, 2022].

In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an n-node graph arrive in an arbitrary order to a machine with a relatively small space, and the goal is to design an algorithm that outputs, as a stream, a proper coloring of the edges using the fewest possible number of colors. Behnezhad et al. [Behnezhad et al., 2019] devised the first non-trivial algorithm for this problem, which computes in Õ(n) space a proper O(Δ²)-coloring w.h.p. (here Δ is the maximum degree of the graph). Subsequent papers improved upon this result, where latest of them [Ansari et al., 2022] showed that it is possible to deterministically compute an O(Δ²/s)-coloring in O(ns) space. However, none of the improvements succeeded in reducing the number of colors to O(Δ^{2-ε}) while keeping the same space bound of Õ(n). In particular, no progress was made on the question of whether computing an O(Δ)-coloring is possible with roughly O(n) space, which was stated in [Behnezhad et al., 2019] to be an interesting open problem. In this paper we bypass the quadratic bound by presenting a new randomized Õ(n)-space algorithm that uses Õ(Δ^{1.5}) colors.

Given a directed graph G = (V, E, ω) on n vertices with positive edge weights as well as two designated terminals s, t ∈ V, our goal is to compute the shortest path from s to t avoiding any pair of presumably failed edges f1,f2 ∈ E, which is a natural generalization of the classical replacement path problem which considers single edge failures only.

Dynamic all-pairs shortest paths is a well-studied problem in the field of dynamic graph algorithms. More specifically, given a directed weighted graph G = (V, E, ω) on n vertices which undergoes a sequence of vertex or edge updates, the goal is to maintain distances between any pair of vertices in V. In a classical work by [Demetrscu and Italiano, 2004], the authors showed that all-pairs shortest paths can be maintained deterministically in amortized Õ(n2) time1, which is nearly optimal. For worst-case update time guarantees, so far the best randomized algorithm has Õ(n3-1/3) time [Abraham, Chechik, Krinninger, 2017], and the best deterministic algorithm needs Õ(n3-2/7) time [Probst Gutenberg, Wulff-Nilsen, 2020]. We provide a faster deterministic worst-case update time of Õ(n3-20/61) for fully dynamic all-pairs shortest paths. To achieve this improvement, we study a natural variant of this problem where a hop constraint is imposed on shortest paths between vertices; that is, given a parameter h, the h-hop shortest path between any pair of vertices s,t ∈ V is a path from s to t with at most h edges whose total weight is minimized. As a result which might be of independent interest, we give a deterministic algorithm that maintains all-pairs h-hop shortest paths under vertex deletions in total update time Õ(n3h + Kn2n2), where K bounds the total number of vertex deletions. * This publication is part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 803118 UncertainENV). 1 Õ(·) hides poly-log factors.

An f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 1 is a data structure that preprocesses a given undirected, unweighted graph G with n vertices and m edges, and a positive integer f. When queried with a pair of vertices s, t and a set F of at most f edges, it returns a σ-approximation of the s-t-distance in G−F.

In a weighed directed graph $G=(V, E, \omega)$ with m edges and n vertices, we are interested in its basic graph parameters such as diameter, radius and eccentricities, under the nonstandard measure of min-distance which is defined for every pair of vertices $u, v \in V$ as the minimum of the shortest path distances from u to v and from v to u. Similar to standard shortest paths distances, computing graph parameters exactly in terms of min-distances essentially requires $\tilde{\Omega}(m n)$ time under plausible hardness conjectures1. Hence, for faster running time complexities we have to tolerate approximations. Abboud, Vassilevska Williams and Wang [SODA 2016] were the first to study min-distance problems, and they obtained constant factor approximation algorithms in acyclic graphs, with running time $\tilde{O}(m)$ and $\tilde{O}(m \sqrt{n})$ for diameter and radius, respectively. The time complexity of radius in acyclic graphs was recently improved to $\tilde{O}(m)$ by Dalirrooyfard and Kaufmann [ICALP 2021], but at the cost of an $O(\log n)$ approximation ratio. For general graphs, the authors of [DWV+, ICALP 2019] gave the first constant factor approximation algorithm for diameter, radius and eccentricities which runs in time $\tilde{O}(m \sqrt{n})$; besides, for the diameter problem, the running time can be improved to $\tilde{O}(m)$ while blowing up the approximation ratio to $O(\log n)$. A natural question is whether constant approximation and near-linear time can be achieved simultaneously for diameter, radius and eccentricities; so far this is only possible for diameter in the restricted setting of acyclic graphs. In this paper, we answer this question in the affirmative by presenting near-linear time algorithms for all three parameters in general graphs.1As usual, the $\tilde{O}(\cdot)$ notation hides poly-logarithmic factors in n

Graph spanners have been extensively studied in the literature of graph algorithms. In an undirected weighted graph G = (V, E,ω) on n vertices, a t-spanner of G is a subgraph that preserves pairwise distances up to a multiplicative stretch factor of t . It is well-known that, for any integer k, a (2k - 1)-spanner with O(n1+1/k ) edges always exists, and the stretch-sparsity balance is tight under the girth conjecture by Erdos. In this paper, we are interested in efficient algorithms for spanners in the distributed setting. Specifically, we present constant-round congested clique algorithms for spanners with nearly optimal stretch-sparsity trade-offs: (2k-1)-spanners with O(n1+1/k ) edges in unweighted graphs (i.e. ω ≡ 1). (1 + ε) (2k - 1)-spanners with O(n1+1/k ) edges in weighted graphs. (2k-1)-spanners withO(kn1+1/k ) edges in weighted graphs.

Let G = (V, E) be an unweighted undirected graph on n vertices and m edges. For a fixed pair of real values α ≥ 1, β ≥ 0, an (α, β) distance oracle of G is a space-efficient data structure that answers, in constant time, for any pair of vertices u,v ∊ V a distance estimate within the range of [dist(u, v), α·dist(u, v) + β]; here dist denotes distances in the graph G. Two main concerns in designing distance oracles are the approximation ratio (the stretch) and the construction time. A classical result was given in [Baswana, Goyaland and Sen 2005] which builds a (2, 3) distance oracle with Õ(n5/3) space in Õ(n2) time. Recently, [Akav and Roditty, 2020] broke the quadratic running time at the expense of increasing the stretch. More specifically, they obtained an algorithm that constructs a (2 + ∊, 5) distance oracle with space Õ(n11/6) in O(m + n2–Ω(∊)) time for any constant ∊ ∊ (0, 1/2). In this paper, we show that one can beat the quadratic running time without compromising on the stretch. More specifically, our algorithm constructs, with high probability, a (2, 3) distance oracle with Õ(n5/3) space in Õ(m+n1.987) time. As a secondary extension, we could further reduce the preprocessing time to Õ(m+n7/4+∊) by tolerating a (2, O(1/∊)) stretch, for any constant ∊ > 0. Finally, this preprocessing time could be pushed even further to Õ(m + n5/3+∊) if we allow a stretch of (2 + ∊, c), where c = c(∊) is a constant depending exponentially on 1/∊.

In this paper we provide a Õ(n2) time algorithm that computes a 2-multiplicative approximation of the girth of an n-node m-edge directed graph with non-negative edge weights. We also provide an additional algorithm that computes a 2-multiplicative approximation of the girth in time 1. Our results naturally provide algorithms for improved constructions of 4-roundtrip spanners, the analog of spanners in directed graphs. Our algorithm is optimal (up to a log n factor) for dense graphs with m = Θ(n2). For comparison, previously, the best approximation ratio with a similar running time for dense graphs was O(log n log log n) [1]. Moreover, unlike previous algorithms, our algorithm neither assumes integer weights, nor does it depend on the maximum edge weight of the graph.

Given a directed graph G = (V, E, ω) with positive integer edge weights that undergoes a sequence of edge insertions, we are interested in maintaining approximate single-source shortest paths in the incremental graph G. In a very recent paper, [Gutenberg et al., 2020] proposed a deterministic algorithm for this problem with Õ(n2 log W) total update time, where n = |V| and W denotes the maximum edge weight. When the underlying graph is super dense, namely, the total number of insertions m is , their upper bound is essentially optimal. For sparse graphs, the only known result is due to [Henzinger et al., 2014], whose algorithm is randomized and works in Õ(mn0.9 log W) total update time under the assumption of oblivious non-adaptive adversary. In this work, we provide two algorithms for this problem when the graph is sparse. The first one is a simple deterministic algorithm with Õ(m5/3 log W) total update time. The second one is a randomized algorithm with Õ ((mn1/2 + m7/5) log W) total update time, which improves over both previous results when m = O(n1.42); moreover, this randomized algorithm plays against adaptive adversaries. Our algorithms are the first to break the O(mn) bound with adaptive adversaries for sparse graphs.

In the Single Source Replacement Paths (SSRP) problem we are given a graph G = (V, E), and a shortest paths tree K̂ rooted at a node s, and the goal is to output for every node t ∈ V and for every edge e in K̂ the length of the shortest path from s to t avoiding e. We present an Õ(m√n + n²) time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed. Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting. Our algorithm naturally extends to the case of small, rational edge weights. In the full version of the paper, we strengthen the existing conditional lower bounds in this case by showing that any O(mn^(1/2-ε)) time (combinatorial or algebraic) algorithm for some fixed ε > 0 yields a truly sub-cubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting).

In the replacement paths (RP) problem we are given a graph G and a shortest path P between two nodes s and t . The goal is to find for every edge e ∈ P, a shortest path from s to t that avoids e. The first result of this paper is a simple reduction from the RP problem to the problem of computing shortest cycles for all nodes on a shortest path. Using this simple reduction we unify and extremely simplify two state of the art solutions for two different well-studied variants of the RP problem. In the first variant (algebraic) we show that by using at most n queries to the Yuster-Zwick distance oracle [FOCS 2005], one can solve the the RP problem for a given directed graph with integer edge weights in the range [-M,M] in Õ(M n^ω) time . This improves the running time of the state of the art algorithm of Vassilevska Williams [SODA 2011] by a factor of log⁶n. In the second variant (planar) we show that by using the algorithm of Klein for the multiple-source shortest paths problem (MSSP) [SODA 2005] one can solve the RP problem for directed planar graph with non negative edge weights in O (n log n) time. This matches the state of the art algorithm of Wulff-Nilsen [SODA 2010], but with arguably much simpler algorithm and analysis.

We improve the time complexity of the single-source shortest path problem for weighted directed graphs (with non-negative integer weights) in the Broadcast CONGEST model of distributed computing. For polynomially bounded edge weights, the state-of-the-art algorithm for this problem requires [EQUATION] rounds [Forster and Nanongkai, FOCS 2018], which is quite far from the known lower bound of [EQUATION] rounds [Elkin, STOC 2014]; here D is the diameter of the underlying network and n is the number of vertices in it. For the approximate version of this problem, Forster and Nanongkai [FOCS 2018] obtained an upper bound of [EQUATION], and stated that achieving the same bound for the exact case remains a major open problem.

Low-stretch spanning tree has been an important graphtheoretic object, as it is one of the building blocks for fast algorithms that solve symmetrically diagonally dominant linear systems, and a significant line of research has been devoted to finding constructions with optimal average stretch. In a very recent work by Goranci and Forster [STOC 2019], the authors initiated the study of low-stretch spanning trees in the dynamic setting, and they proposed a dynamic algorithm that maintains a spanning tree in amortized update time with subpolynomial stretch in an unweighted graph on n vertices undergoing edge insertions and deletions demanded by an oblivious adversary. Our main results are twofold. First, we substantially improve the update time of Goranci and Forster [STOC 2019] from to a subpolynomial of no(1). Second, we generalize our result to weighted graphs under the decremental setting. As far as we know, this is the first non trivial dynamic algorithm for maintaining low-stretch spanning tree for weighted graphs.

We present the first distance sensitivity oracle (DSO) with subcubic preprocessing time and poly-logarithmic query time for directed graphs with integer weights in the range [−M,M].

In this paper we provide a Õ(m√n) time algorithm that computes a 3-multiplicative approximation of the girth of a n-node m-edge directed graph with non-negative edge lengths. This is the first algorithm which approximates the girth of a directed graph up to a constant multiplicative factor faster than All-Pairs Shortest Paths (APSP) time, i.e. O(mn). Additionally, for any integer k ≥ 1, we provide a deterministic algorithm for a O(kloglogn)-multiplicative approximation to the girth in directed graphs in Õ(m 1+1/k ) time. Combining the techniques from these two results gives us an algorithm for a O(klogk)-multiplicative approximation to the girth in directed graphs in Õ(m 1+1/k ) time. Our results naturally also provide algorithms for improved constructions of roundtrip spanners, the analog of spanners in directed graphs.

In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph G while edges are inserted and deleted from the graph. The first non-trivial algorithm for this problem was presented by Assadi, Onak, Schieber, and Solomon [STOC 2018] who obtained a deterministic fully dynamic MIS with O(m3/4) update time. Later, this was independently improved by Du and Zhang and by Gupta and Khan [arXiv 2018] to Õ(m2/3) update time1Du and Zhang [arXiv 2018] also presented a randomized algorithm against an oblivious adversary with Õ(√m) update time. The current state of art is by Assadi, Onak, Schieber, and Solomon [SODA 2019] who obtained randomized algorithms against oblivious adversary with Õ(√n) and Õ(m1/3) update times. In this paper, we propose a dynamic randomized algorithm against oblivious adversary with expected worst-case update time of O(log4n). As a direct corollary, one can apply the black-box reduction from a recent work by Bernstein, Forster, and Henzinger [SODA 2019] to achieve O(log6n) worst-case update time with high probability. This is the first dynamic MIS algorithm with very fast update time of poly-log.

In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O~(m sqrt{n}). Here we provide the first deterministic algorithm for this problem, with the same O~(m sqrt{n}) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of O~(mn) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in O~(m sqrt{n}) time, and a deterministic algorithm for the k-simple shortest paths problem in O~(k m sqrt{n}) time (for any integer constant k > 0). For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t in V and F subseteq E cup V, |F| <=f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \ F (i.e., the distance from s to t in the graph G after removing from it the failing edges and vertices F). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized f-DSOs. In particular, they presented a combinatorial f-DSO with O~(mn^{4-alpha}) preprocessing time and subquadratic O~(n^{2-2(1-alpha)/f}) query time, giving a tradeoff between preprocessing and query time for every value of 0 < alpha < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time.

The Single Source Replacement Paths (SSRP) problem is as follows; Given a graph G = (V, E), a source vertex s and a shortest paths tree Ts rooted in s, output for every vertex t ∊ V and for every edge e in Ts the length of the shortest path from s to t avoiding e. We present near optimal upper bounds, by providing time randomized combinatorial algorithm 1 for unweighted undirected graphs, and matching conditional lower bounds for the SSRP problem.

In this paper, we consider distributed coloring for planar graphs with a small number of colors. Our main result is an optimal (up to a constant factor) O(log n) time algorithm for 6-coloring planar graphs. Our algorithm is based on a novel technique that in a nutshell detects small structures that can be easily colored given a proper coloring of the rest of the vertices and removes them from the graph until the graph contains a small enough number of edges. We believe this technique might be of independent interest. In addition, we present a lower bound for 4-coloring planar graphs that essentially shows that any algorithm (deterministic or randomized) for 4-coloring planar graphs requires Ω(n) rounds. We therefore completely resolve the problems of 4-coloring and 6-coloring for planar graphs in the LOCAL model.

In this paper we study the time complexity of the single-source reachability problem and the single-source shortest path problem for directed unweighted graphs in the Broadcast CONGEST model. We focus on the case where the diameter D of the underlying network is constant. We show that for the case where D = 1 there is, quite surprisingly, a very simple algorithm that solves the reachability problem in 1(!) round. In contrast, for networks with D = 2, we show that any distributed algorithm (possibly randomized) for this problem requires Omega(sqrt{n/ log{n}}) rounds. Our results therefore completely resolve (up to a small polylog factor) the complexity of the single-source reachability problem for a wide range of diameters. Furthermore, we show that when D = 1, it is even possible to get an almost 3 - approximation for the all-pairs shortest path problem (for directed unweighted graphs) in just 2 rounds. We also prove a stronger lower bound of Omega(sqrt{n}) for the single-source shortest path problem for unweighted directed graphs that holds even when the diameter of the underlying network is 2. As far as we know this is the first lower bound that achieves Omega(sqrt{n}) for this problem.

Clustering of data points is a fundamental tool in data analysis. We consider points X in a relaxed metric space, where the triangle inequality holds within a constant factor. A clustering of X is a partition of X defined by a set of points Q(centroids), according to the closest centroid. The cost of clustering X by Q is V(Q)= ∑x ∈ X dxQ. This formulation generalizes classic k-means clustering, which uses squared distances. Two basic tasks, parametrized by k ≥ 1, are cost estimation, which returns (approximate) V(Q) for queries Q such that |Q| = k and clustering, which returns an (approximate) minimizer of V(Q) of size |Q|= k. When the data set X is very large, we seek efficient constructions of small samples that can act as surrogates for performing these tasks. Existing constructions that provide quality guarantees, however, are either worst-case, and unable to benefit from structure of real data sets, or make explicit strong assumptions on the structure. We show here how to avoid both these pitfalls using adaptive designs. The core of our design are the novel one2all probabilities, computed for a set M of centroids and α ≥ 1: The clustering cost of each Q with cost V(Q) ≥ V(M)/α can be estimated well from a sample of size O(α |M| ε-2). For cost estimation, we apply one2all with a bicriteria approximate M, while adaptively balancing |M| and α to optimize sample size per quality. For clustering, we present a wrapper that adaptively applies a base clustering algorithm to a sample S, using the smallest sample that provides the desired statistical guarantees on quality. We demonstrate experimentally the huge gains of using our adaptive instead of worst-case methods.

In this paper we consider the decremental approximate all-pairs shortest paths (APSP) problem, where given a graph G the goal is to maintain approximate shortest paths between all pairs of nodes in G under a sequence of online adversarial edge deletions. We present a decremental APSP algorithm for undirected weighted graphs with (2+ε)k-1 stretch, O(mn1/k +o(1)log(nW)) total update time and O(log log(n W)) query time for a fixed constant ε, where W is the maximum edge weight (assuming the minimum edge weight is 1) and k is any integer parameter. This is an exponential improvement both in the stretch and in the query time over previous works.

We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic $(2+ε)$-approximate integral matching algorithm with small polylog worst-case update time. For the $(2+ε)$-approximation regime only a \emph{fractional} fully-dynamic $(2+ε)$-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al.~(SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm.

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.

In the incremental cycle detection problem edges are inserted to a directed graph (initially empty) and the algorithm has to report once a directed cycle is formed in the graph. A closely related problem to the incremental cycle detection is that of the incremental topological sort problem, in which edges are inserted to an acyclic graph and the algorithm has to maintain a valid topological sort on the vertices at all times. Both incremental cycle detection and incremental topological sort have a long history. The state of the art is a recent breakthrough of Bender, Fineman, Gilbert and Tarjan [TALG 2016], with two different algorithms with respective total update times of Õ(n2) and O(m · min{m1/2, n2/3}). The two algorithms work for both incremental cycle detection and incremental topological sort. In this paper we introduce a novel technique that allows us to improve upon the state of the art for a wide range of graph sparsity. Our algorithms has a total expected update time of for both the incremental cycle detection and the topological sort problems.

A spanner H of a weighted undirected graph G is a “sparse” subgraph that approximately preserves distances between every pair of vertices in G . We refer to H as a δ-spanner of G for some parameter δ ≥ 1 if the distance in H between every vertex pair is at most a factor δ bigger than in G . In this case, we say that H has stretch δ. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). It is well-known that for any positive integer k , one can efficiently construct a (2 k − 1)-spanner of G with O ( n 1+1/ k ) edges where n is the number of vertices [2]. This size-stretch tradeoff is conjectured to be optimal based on a girth conjecture of Erdős [17]. However, the current state of the art for the second measure is not yet optimal. Recently Elkin, Neiman and Solomon [ICALP 14] presented an improved analysis of the greedy algorithm, proving that the greedy algorithm admits (2 k − 1) · (1 + ϵ) stretch and total edge weight of O ϵ (( k / log k ) · ω ( MST ( G )) · n 1/ k ), where ω( MST ( G )) is the weight of a MST of G . The previous analysis by Chandra et al. [SOCG 92] admitted (2 k − 1) · (1 + ϵ) stretch and total edge weight of O ϵ ( k ω( MST ( G )) n 1/ k ). Hence, Elkin et al. improved the weight of the spanner by a log k factor. In this article, we completely remove the k factor from the weight, presenting a spanner with (2 k − 1) · (1 + ϵ) stretch, O ϵ (ω( MST ( G )) n 1/ k ) total weight, and O ( n 1+1/ k ) edges. Up to a (1 + ϵ) factor in the stretch this matches the girth conjecture of Erdős [17].

We revisit the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph. The allowed updates are insertions and deletions of nodes and their incident edges. We give worst- case guarantees on the time needed to process a single update (in contrast to related results, the update time is not amortized over a sequence of updates). Our main result is a simple randomized algorithm that for any parameter c > 1 has a worst-case update time of O(cn2+2/3 log4/3 n) and answers distance queries correctly with probability 1 — 1/nc, against an adaptive online adversary if the graph contains no negative cycle. The best deterministic algorithm is by Thorup [STOC 2005] with a worst-case update time of Õ(n2+3/4) and assumes non-negative weights. This is the first improvement for this problem for more than a decade. Conceptually, our algorithm shows that randomization along with a more direct approach can provide better bounds.

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions. (Our algorithm can also be modified to work in the incremental setting, where the graph is initially empty and subject to a sequence of online adversarial edge insertions.) In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O (mn) total update time over all edge deletions. Later papers presented conditional lower bounds showing that O(mn) is optimal up to log factors. In SODA 2011, Bernstein and Roditty showed how to bypass these lower bounds and improve upon the Even and Shiloach O(mn) total update time bound by allowing a (1 + ∊) approximation. This triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a (1 + ∊)-approximate algorithm whose total update time is near linear: However, every single one of these improvements over the Even-Shiloach algorithm was randomized and assumed a non-adaptive adversary. This additional assumption meant that the algorithms were not suitable for certain settings and could not be used as a black box data structure. Very recently Bernstein and Chechik presented in STOC 2016 the first deterministic improvement over Even and Shiloach, that did not rely on randomization or assumptions about the adversary: in an undirected unweighted graph the algorithm maintains (1+ ∊)-approximate distances and has total update time O(n2). In this paper, we present a new deterministic algorithm for the problem with total update time Õ(n1.25√m) = Õ (mn3/4): it returns a (1 + ∊) approximation, and is limited to undirected unweighted graphs. Although this result is still far from matching the randomized near-linear total update time, it presents important progress towards that direction, because unlike the STOC 2016 Õ (n2) algorithm it beats the Even and Shiloach Õ (mn) bound for all graphs, not just sufficientl6y dense ones. In particular, the Õ (n2) algorithm relied entirely on a new sparsification technique, and so could not hope to yield an improvement for sparse graphs. We present the first deterministic improvement for sparse graphs by significantly extending some of the ideas from the Õ (n2) algorithm and combining them with the hop-set technique used in several earlier dynamic shortest path papers. Also, because decremental single source shortest paths is often used as a building block for fully dynamic all pairs shortest paths, using our new algorithm as a black box yields new deterministic algorithms for fully dynamic approximate all pairs shortest paths.

An f-Sensitive Distance Oracle with stretch a preprocesses a graph G(V, E) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set F ⊂ E of at most f edges, and vertices s and t. The oracle answers a query (F,s.,t) by returning a value d which is equal to the length of some path between s and t in the graph G\F (the graph obtained from G by discarding all edges in F). Moreover, d is at most a times the length of the shortest path between s and t in G \ F. The oracle can also construct a path between s and t in G\F of length d. To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any and a fixed ∊ > 0 our oracle answers queries (F,s,t) in time O(l) with (1 + ∊) stretch using a data structure of size n2+0(1) For comparison, the naive alternative requires mfn2 space for sublinear query time.

Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especially for directed graphs. A directed graph is 2-edge-connected (resp., 2-vertex-connected) if the removal of any edge (resp., vertex) leaves the graph strongly connected. In this paper we present improved algorithms for computing the maximal 2-edge- and 2- vertex-connected subgraphs of a given directed graph. These problems were first studied more than 35 years ago, with Õ(mn) time algorithms for graphs with m edges and n vertices being known since the late 1980s. In contrast, the same problems for undirected graphs are known to be solvable in linear time. Henzinger et al. [ICALP 2015] recently introduced O(n2) time algorithms for the directed case, thus improving the running times for dense graphs. Our new algorithms run in time O(m3/2), which further improves the running times for sparse graphs. The notion of 2-connectivity naturally generalizes to k-connectivity for k > 2. For constant values of k, we extend one of our algorithms to compute the maximal k-edge-connected in time O(m3/2 logn), improving again for sparse graphs the best known algorithm by Henzinger et al. [ICALP 2015] that runs in O(n2 log n) time.

We present randomized algorithms with a total update time of Õ(m √n) for the problems of decremental single source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler.

Given a base weighted planar graph Ginput on n nodes and parameters M, ∊ we present a dynamic distance oracle with 1 + ∊ stretch and worst case update and query costs of ∊–3M4 · poly-log(n). We allow arbitrary edge weight updates as long as the shortest path metric induced by the updated graph has stretch of at most M relative to the shortest path metric of the base graph Ginput. For example, on a planar road network, we can support fast queries and dynamic traffic updates as long as the shortest path from any source to any target (including using arbitrary detours) is between, say, 80 and 3 miles-per-hour. As a warm-up we also prove that graphs of bounded treewidth have exact distance oracles in the dynamic edge model. To the best of our knowledge, this is the first dynamic distance oracle for a non-trivial family of dynamic changes to planar graphs with worst case costs of o(n1/2) both for query and for update operations.

A spanner H of a weighted undirected graph G is a “sparse” subgraph that approximately preserves distances between every pair of vertices in G. We refer to H as a δ-spanner of G for some parameter δ ≥ 1 if the distance in H between every vertex pair is at most a factor δ bigger than in G. In this case, we say that H has stretch δ. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). It is well-known that for any positive integer k, one can efficiently construct a (2k – 1)-spanner of G with O(n1+1/k) edges where n is the number of vertices [2]. This size-stretch tradeoff is conjectured to be optimal based on a girth conjecture of Erdős [17]. However, the current state of the art for the second measure is not yet optimal. Recently Elkin, Neiman and Solomon [ICALP 14] presented an improved analysis of the greedy algorithm, proving that the greedy algorithm admits (2k – 1) · (1 + ∊) stretch and total edge weight of O∊((k/log k) · ω(MST(G)) · n1/k), where ω(MST(G)) is the weight of a minimum spanning tree of G. The previous analysis by Chandra et al. [SOCG 92] admitted (2k – 1) · (1 + ∊) stretch and total edge weight of O∊(kω(MST(G))n1/k). Hence, Elkin et al. improved the weight of the spanner by a log k factor. In this work, we complectly remove the k factor from the weight, presenting a spanner with (2k – 1) · (1 + ∊) stretch, O∊(ω(MST(G))n1/k) total weight, and O(n1+1/k) edges. Up to a (1 + ∊) factor in the stretch this matches the girth conjecture of Erdős [17].

Gabow and Tarjan showed that the Bottleneck Path (BP) problem, i.e., finding a path between a given source and a given target in a weighted directed graph whose largest edge weight is minimized, as well as the Bottleneck spanning tree (BST) problem, i.e., finding a directed spanning tree rooted at a given vertex whose largest edge weight is minimized, can both be solved deterministically in O(m * log^*(n)) time, where m is the number of edges and n is the number of vertices in the graph. We present a slightly improved randomized algorithm for these problems with an expected running time of O(m * beta(m,n)), where beta(m,n) = min{k >= 1 | log^{(k)}n <= m/n } <= log^*(n) - log^*(m/n)+1. This is the first improvement for these problems in over 25 years. In particular, if m >= n * log^{(k)} * n, for some constant k, the expected running time of the new algorithm is O(m). Our algorithm, as that of Gabow and Tarjan, work in the comparison model. We also observe that in the word-RAM model, both problems can be solved deterministically in O(m) time. Finally, we solve an open problem of Andersson et al., giving a deterministic O(m)-time comparison-based algorithm for solving deterministic 2-player turn-based zero-sum terminal payoff games, also known as Deterministic Graphical Games (DGG).

In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions.

This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by α. For an n -vertex graph G in this family, and for any desired precision parameter ϵ > 0, the labeling scheme stores an O (1 + ϵ − 1 ) 2α log 2 n -bit label at each vertex. Given the labels of two end-vertices s and t , and the labels of a set F of “forbidden” vertices and/or edges, our scheme can compute, in O (1 + ϵ − 1 ) 2α · | F | 2 log n time, a 1 + ϵ stretch approximation for the distance between s and t in the graph G ∖ F . The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + ϵ for graphs of bounded doubling dimension.

We investigate the problem of approximate Nearest-Neighbor Search (NNS) in graphical metrics: The task is to preprocess an edge-weighted graph G=(V,E) on m vertices and a small "dataset" D \subset V of size n << m, so that given a query point q \in V, one can quickly approximate dist(q,D) (the distance from q to its closest vertex in D) and find a vertex a \in D within this approximated distance. We assume the query algorithm has access to a distance oracle, that quickly evaluates the exact distance between any pair of vertices. For planar graphs G with maximum degree Delta, we show how to efficiently construct a compact data structure -- of size ~O(n(Delta+1/epsilon)) -- that answers (1+epsilon)-NNS queries in time ~O(Delta+1/epsilon). Thus, as far as NNS applications are concerned, metrics derived from bounded-degree planar graphs behave as low-dimensional metrics, even though planar metrics do not necessarily have a low doubling dimension, nor can they be embedded with low distortion into l_2. We complement our algorithmic result by lower bounds showing that the access to an exact distance oracle (rather than an approximate one) and the dependency on Delta (in query time) are both essential.

The average distance from a node to all other nodes in a graph, or from a query point in a metric space to a set of points, is a fundamental quantity in data analysis. The inverse of the average distance, known as the (classic) closeness centrality of a node, is a popular importance measure in the study of social networks. We develop novel structural insights on the sparsifiability of the distance relation via weighted sampling. Based on that, we present highly practical algorithms with strong statistical guarantees for fundamental problems. We show that the average distance (and hence the centrality) for all nodes in a graph can be estimated using O(epsilon^{-2}) single-source distance computations. For a set V of n points in a metric space, we show that after preprocessing which uses O(n) distance computations we can compute a weighted sample S subset of V of size O(epsilon^{-2}) such that the average distance from any query point v to V can be estimated from the distances from v to S. Finally, we show that for a set of points V in a metric space, we can estimate the average pairwise distance using O(n+epsilon^{-2}) distance computations. The estimate is based on a weighted sample of O(epsilon^{-2}) pairs of points, which is computed using O(n) distance computations. Our estimates are unbiased with normalized mean square error (NRMSE) of at most epsilon. Increasing the sample size by a O(log(n)) factor ensures that the probability that the relative error exceeds epsilon is polynomially small.

A distance oracle is a compact data structure capable of quickly estimating distances in a given graph. In this paper we provide a new construction for distance oracles in general undirected weighted graphs. Our data structure, for any integer k, requires O( n1+1/k) space, guarantees a stretch of 2k-1, and answers any query in only O(1) time.

Much of social network analysis is---implicitly or explicitly---predicated on the assumption that individuals tend to be more similar to their friends than to strangers. Thus, an observed social network provides a noisy signal about the latent underlying “social space''---the way in which individuals are similar or dissimilar. Many research questions frequently addressed via social network analysis are in reality questions about this social space, raising the question of inverting the process: Given a social network, how accurately can we reconstruct the social structure of similarities and dissimilarities? We begin to address this problem formally. Observed social networks are usually multiplex, in the sense that they reflect (dis)similarities in several different “categories,” such as geographical proximity, kinship, or similarity of professions/hobbies. We assume that each such category is characterized by a latent metric capturing (dis)similarities in this category. Each category gives rise to a separate social network: a random graph parameterized by this metric. For a concrete model, we consider Kleinberg's small world model and some variations thereof. The observed social network is the unlabeled union of these graphs; i.e., the presence or absence of edges can be observed, but not their origins. Our main result is an efficient algorithm which reconstructs each metric with provably low distortion.

A fully dynamic approximate distance oracle is a distance reporting data structure that supports dynamic insert edge and delete edge operations. In this paper we break a longstanding barrier in the design of fully dynamic all-pairs approximate distance oracles. All previous results for this model incurred an amortized cost of at least Omega(n) per operation. We present the first construction that provides constant stretch and o(m) amortized update time. For graphs that are not too dense (where |E| = O(|V|^{2-delta}) for some delta>0 we break the O(n) barrier and provide the first construction with constant stretch and o(n) amortized cost.

The diameter is a fundamental graph parameter and its computation is necessary in many applications. The fastest known way to compute the diameter exactly is to solve the All-Pairs Shortest Paths (APSP) problem. In the absence of fast algorithms, attempts were made to seek fast algorithms that approximate the diameter. In a seminal result Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] designed an algorithm that computes in time an estimate for the diameter D in directed graphs with nonnegative edge weights, such that ⌊⅔ · D⌋ – (M – 1) ≤ ≤ D, where M is the maximum edge weight in the graph. In recent work, Roditty and Vassilevska W. [STOC 13] gave a Las Vegas algorithm that has the same approximation guarantee but improves the (expected) runtime to . Roditty and Vassilevska W. also showed that unless the Strong Exponential Time Hypothesis fails, no (n2−∊) time algorithm for sparse unweighted undirected graphs can achieve an approximation ratio better than . Thus their algorithm is essentially tight for sparse unweighted graphs. For weighted graphs however, the approximation guarantee can be meaningless, as M can be arbitrarily large. In this paper we exhibit two algorithms that achieve a genuine -approximation for the diameter, one running in time, and one running in time. Furthermore, our algorithms are deterministic, and thus we present the first deterministic (2 – ∊)-approximation algorithm for the diameter that takes subquadratic time in sparse graphs. In addition, we address the question of obtaining an additive c-approximation for the diameter, i.e. an estimate such that D – c ≤ ≤ D. An extremely simple time algorithm achieves an additive n∊-approximation; no better results are known. We show that for any ∊ > 0, getting an additive n∊-approximation algorithm for the diameter running in (n2−δ) time for any δ > 2∊ would falsify the Strong Exponential Time Hypothesis. Thus the simple algorithm is probably essentially tight for sparse graphs, and moreover, obtaining a subquadratic time additive c-approximation for any constant c is unlikely. Finally, we consider the problem of computing the eccentricities of all vertices in an undirected graph, i.e. the largest distance from each vertex. Roditty and Vassilevska W. [STOC 13] show that in time, one can compute for each v ∊ V in an undirected graph, an estimate ∊(v) for the eccentricity ∊(v) such that max {R, · ∊(v)} ≤ ∊(v) ≤ min {D, · ∊(v)} where R = minv ∊(v) is the radius of the graph. Here we improve the approximation guarantee by showing that a variant of the same algorithm can achieve estimates ∊′(v) with · ∊(v) ≤ ∊′(v) ≤ ∊(v).

An approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes of a given graph.

We consider the problem of compact routing in weighted general undirected graphs, in which the goal is to construct local routing tables that allow information to be sent on short paths in the network. In this paper the first improvement to the work of Thorup and Zwick [SPAA'01] is presented. Specifically, we construct an improved routing scheme obtaining for every k routing tables of size Õ(n1/k log D), and stretch (4 -- α)k -- β for some absolute constants α, β > 0, where D is the normalized diameter. This provides a positive answer to a main open question in this area as to the existence of a routing scheme with stretch c • k for some constant c < 4.

Much of social network analysis is — implicitly or explicitly — predicated on the assumption that individuals tend to be more similar to their friends than to strangers. Thus, an observed social network provides a noisy signal about the latent underlying “social space:” the way in which individuals are similar or dissimilar. Many research questions frequently addressed via social network analysis are in reality questions about this social space, raising the question of inverting the process: Given a social network, how accurately can we reconstruct the social structure of similarities and dissimilarities? We begin to address this problem formally. Observed social networks are usually multiplex, in the sense that they reflect (dis)similarities in several different “categories,” such as geographical proximity, kinship, or similarity of professions/hobbies. We assume that each such category is characterized by a latent metric capturing (dis)similarities in this category. Each category gives rise to a separate social network: a random graph parameterized by this metric. For a concrete model, we consider Kleinberg's small world model and some variations thereof. The observed social network is the unlabeled union of these graphs, i.e., the presence or absence of edges can be observed, but not their origins. Our main result is a near-linear time algorithm which reconstructs each metric with provably low distortion.

This paper considers additive and purely additive spanners. We present a new purely additive spanner of size Õ(n7/5) with additive stretch 4. This construction fills in the gap between the two existing constructions for purely additive spanners, one for 2-additive spanner of size O(n3/2) and the other for 6-additive spanner of size O(n4/3), and thus answers a main open question in this area. In addition, we present a construction for additive spanners with Õ(n1+δ) edges and additive stretch of O(n1/2–3δ/2) for any 3/17 ≤ δ < 1/3, improving the stretch of the existing constructions from O(n1–3δ) to . Finally, we show that our (1, n1/2–3δ/2)-spanner construction can be tweaked to give a sublinear additive spanner of size O(n1+3/17) with additive stretch .

This paper considers fully dynamic (1+ε) distance oracles and (1+ε) forbidden-set labeling schemes for planar graphs. For a given n-vertex planar graph G with edge weights drawn from [1,M] and parameter ε>0, our forbidden-set labeling scheme uses labels of length λ = O(ε-1 log2n log(nM) • maxlogn). Given the labels of two vertices s and t and of a set F of faulty vertices/edges, our scheme approximates the distance between s and t in G \ F with stretch (1+ε), in O(|F|2 λ) time.

The paper proposes a forbidden-set labeling scheme for the family of graphs with doubling dimension bounded by α. For an n-vertex graph G in this family, and for any desired precision parameter ε > 0, the labeling scheme stores an O(1+α-1)2α log2 n-bit label at each vertex. Given the labels of two end-vertices s and t, and the labels of a set F of "forbidden" vertices and/or edges, our scheme can compute, in time polynomial in the length of the labels, a 1+ε stretch approximation for the distance between s and t in the graph GF. The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + ε for graphs of bounded doubling dimension.

In the {\em uncapacitated facility location} problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities $R$, so as to minimize the sum of the cost of opening the facilities in $R$ and the cost of assigning all node demands to open facilities. This paper concerns the {\em robust fault-tolerant} version of the uncapacitated facility location problem (RFTFL). In this problem, one or more facilities might fail, and each demand should be supplied by the closest open facility that did not fail. It is required to find a set of facilities $R$, so as to minimize the sum of the cost of opening the facilities in $R$ and the cost of assigning all node demands to open facilities that did not fail, after the failure of up to $\alpha$ facilities. We present a polynomial time algorithm that yields a 6.5-approximation for this problem with at most one failure and a $1.5 + 7.5\alpha$-approximation for the problem with at most $\alpha > 1$ failures. We also show that the $RFTFL$ problem is NP-hard even on trees, and even in the case of a single failure.

This paper concerns graph spanners that are resistant to vertex or edge failures. In the failure-free setting, it is known how to efficiently construct a $(2k-1)$-spanner of size $O(n^{1+1/k})$, and this size-stretch trade-off is conjectured to be tight. The notion of fault tolerant spanners was introduced a decade ago in the geometric setting [C. Levcopoulos, G. Narasimhan, and M. Smid, in Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 186–195]. A subgraph H is an f-vertex fault tolerant k-spanner of the graph G if for any set $F\subseteq V$ of size at most f and any pair of vertices $u,v\in V\setminus F$, the distances in H satisfy $\delta_{H\setminus F}(u,v)\leq k\cdot\delta_{G\setminus F}(u,v)$. A fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [A. Czumaj and H. Zhao, Discrete Comput. Geom., 32 (2004), pp. 207–230]. This paper also raised as an open problem the question of whether it is possible to obtain a fault tolerant spanner for an arbitrary undirected weighted graph. The current paper answers this question in the affirmative, presenting an f-vertex fault tolerant $(2k-1)$-spanner of size $O(f^{2}k^{f+1}\cdot n^{1+1/k}\log^{1-1/k}n)$. Interestingly, the stretch of the spanner remains unchanged, while the size of the spanner increases only by a factor that depends on the stretch k, on the number of potential faults f, and on logarithmic terms in n. In addition, we consider the simpler setting of f-edge fault tolerant spanners (defined analogously). We present an f-edge fault tolerant $(2k-1)$-spanner with edge set of size $O(f\cdot n^{1+1/k})$ (only f times larger than standard spanners). For both edge and vertex faults, our results are shown to hold when the given graph G is weighted.

The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G=(V,E) and an integer k ≥ 1, the subgraph H=(V,E'), E'⊆ E, is a spanner of stretch k (or, a k-spanner) of G if δH(u,v) ≤ k· δG(u,v) for every u,v ∈ V, where δG'(u,v) denotes the distance between u and v in G'. Graph spanners were extensively studied since their introduction over two decades ago. It is known how to efficiently construct a (2k-1)-spanner of size O(n1+1/k), and this size-stretch tradeoff is conjectured to be tight.