Let G = (V, E) be a graph with n = |V| nodes and m = |E| edges. The t-Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distances between t prespecified pairs of vertices. Recently, this problem has received renewed attention, particularly in the case where t = Θ(n): the n-Pairs Shortest Paths problem. In this setting, new algorithms and conditional lower bounds have been developed by Dalirrooyfard, Jin, Vassilevska Williams, and Wein [FOCS'22], and Chechik, Hoch, and Lifshitz [SODA'25]. In this paper, we present the first algorithm for the n-Pairs Shortest Paths problem in weighted undirected graphs that achieves a (2 - α)k-approximation, for constant α > 0, that runs in Õ(mn^{1/k} + n^{1 + 2/k}) time. Specifically, we present a 1.622k-approximation, improving upon the (2k - 3)-approximation of Chechik, Hoch, and Lifshitz [SODA'25] for graphs that are not super sparse, which answers in the affirmative the open question posed by them. We also develop improved approximation algorithms with better tradeoffs for unweighted graphs and dense weighted graphs that improve upon the results of Dalirrooyfard et al. and Chechik, Hoch, and Lifshitz. Our main technical contribution is the new heavy-edge technique. Using this technique, we transform an algorithm with an approximation guarantee that depends on W_{uv}, the weight of the heaviest edge on the shortest path between u and v, into an algorithm with purely multiplicative approximation that does not depend on W_{uv}.

We study the problem of approximating the length of a shortest cycle in a given graph, known as the girth of the graph. The state-of-the-art approximation algorithms for unweighted graphs by Kadria et al. [SODA'22] and Roditty and Trabelsi [arXiv'25] achieve the following trade-off: for every integer k ≥ 2, there is an Õ(n^{1+2/k}) time algorithm that achieves a (2k/3)-approximation for the girth in unweighted n-node graphs. The first result of this paper is to achieve the same trade-off for m-edge, n-node graphs with non-negative real edge weights: a 2k/3-approximation algorithm running in Õ(m+n^{1+2/k}) time. The dependence on m is unavoidable in weighted graphs. Our result improves on the work of Kadria et al. [SODA'23] and Ducoffe [ICALP'19 and SIDMA'21], who were only able to achieve such a trade-off for some values of k. We also prove new fine-grained lower bounds for girth approximation and related problems in unweighted graphs.

Let $G=(V, E)$ be an undirected $n$-vertices $m$-edges graph with non-negative edge weights. In this paper, we present three new algorithms for constructing a $(2k-1)$-stretch distance oracle with $O(n^{1+\frac{1}{k}})$ space. The first algorithm runs in $\Ot(\max(n^{1+2/k}, m^{1-\frac{1}{k-1}}n^{\frac{2}{k-1}}))$ time, and improves upon the $\Ot(\min(mn^{\frac{1}{k}},n^2))$ time of Thorup and Zwick [STOC 2001, JACM 2005] and Baswana and Kavitha [FOCS 2006, SICOMP 2010], for every $k > 2$ and $m=Ω(n^{1+\frac{1}{k}+\eps})$. This yields the first truly subquadratic time construction for every $2 < k < 6$, and nearly resolves the open problem posed by Wulff-Nilsen [SODA 2012] on the existence of such constructions. The two other algorithms have a running time of the form $\Ot(m+n^{1+f(k)})$, which is near linear in $m$ if $m=Ω(n^{1+f(k)})$, and therefore optimal in such graphs. One algorithm runs in $\Ot(m+n^{\frac32+\frac{3}{4k-6}})$-time, which improves upon the $\Ot(n^2)$-time algorithm of Baswana and Kavitha [FOCS 2006, SICOMP 2010], for $3 < k < 6$, and upon the $\Ot(m+n^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$-time algorithm of Wulff-Nilsen [SODA 2012], for every $k\geq 6$. This is the first linear time algorithm for constructing a $7$-stretch distance oracle and a $9$-stretch distance oracle, for graphs with truly subquadratic density.\footnote{with $m=n^{2-\eps}$ for some $\eps > 0$.} The other algorithm runs in $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{2}}{\sqrt{k}}})$ time, (and hence relevant only for $k\ge 16$), and improves upon the $\Ot(\sqrt{k}m+kn^{1+\frac{2\sqrt{6}}{\sqrt{k}}+O(k^{-1})})$ time algorithm of Wulff-Nilsen [SODA 2012] (which is relevant only for $k\ge 96$). ...

Computing the diameter of a graph is a problem of great interest both in general algorithms research and specifically within fine-grained complexity, where it is a cornerstone hard problem. As computing the exact diameter in m-edge graphs requires m^{2-o(1)} time under the Strong Exponential Time Hypothesis, much work has gone into approximating this parameter. Recent work has achieved a full conditional lower bound tradeoff curve for both directed and undirected graphs [Dalirrooyfard, Li and Vassilevska W., FOCS'21]. However, the best known upper bounds do not match the lower bounds. In particular, the best known approximation scheme for undirected graph diameter [Cairo-Grossi-Rizzi, SODA 2016] has not been improved. Moreover, this scheme is randomized and no similar deterministic scheme is known. Another fundamental field of research in shortest paths computation is the construction of approximate distance oracles. Thorup and Zwick [JACM'05] provided the first such distance oracle with constant query time and (conditionally) optimal space, and in the years since many advances have led to a vast toolbox of techniques and data structures. These two areas of research seem natural to combine since they both concern approximating shortest paths. However, the known diameter approximation algorithms only use a small subset of the techniques used in distance oracles research. In this work we show that in fact approximate diameter and distance oracles are intricately connected. We first demonstrate a strong connection between the current best known diameter approximation scheme of Cairo, Grossi and Rizzi ("CGR") and the (2k-1)-approximate distance oracle of Thorup and Zwick. This allows us to derandomize the CGR algorithm and obtain the first deterministic diameter approximation tradeoff. We further derandomize other central techniques in the field of distance oracles and use them to achieve new deterministic diameter approximation algorithms, including a simpler 3/2-approximation with no additive error and a new 5/3-approximation, the first new step in the diameter approximation tradeoff in almost a decade. Finally, we show how these new techniques can be used to derandomize many current best known results in various fields of shortest paths approximations.

We present a +2∑_{i=1}^{k+1} W_i-APASP algorithm for dense weighted graphs with a runtime of Õ(n^{2+1/(3k+2)), where W_i is the weight of an i^th heaviest edge on a shortest path between two vertices. Dor, Halperin and Zwick [FOCS'96 and SICOMP'00] introduced two algorithms for the commensurate unweighted +2⋅ (k+1)-APASP problem: one for sparse graphs with a runtime of Õ(n^{2-1/(k+2)} m^{1/(k+2)}) and one for dense graphs with a runtime of Õ(n^{2+1/(3k+2)}). Subsequently, Cohen and Zwick [SODA'97 and JALG'01] adapted the algorithm for sparse graphs to the weighted setting, namely a +2∑_{i=1}^{k+1} W_i-APASP algorithm with the same Õ(n^{2-1/(k+2)} m^{1/(k+2)}) runtime. We fill the nearly three decades old gap by providing an algorithm for dense weighted graphs, matching the runtime for the unweighted setting. In addition, we explore nearly additive APASP, where the multiplicative stretch is 1+ε. We present a (1+ε, min{2W₁,4W₂})-APASP algorithm with a runtime of Õ((1/ε)^{O(1)} ⋅ n^{2.15135313} ⋅ log W). This improves upon Saha and Ye [SODA'24], which had the same runtime, yet (1+ε, 2W₁)-APASP. For pure multiplicative APASP, we present a (7/3+ε)-APASP algorithm with a runtime of Õ((1/ε)^{O(1)} ⋅ n^{2.15135313} ⋅ log W). This improves, for dense graphs, the Õ(nm^{2/3}+n²) runtime of the 7/3-APASP algorithm by Baswana and Kavitha [FOCS'06 and SICOMP'10], at the cost of introducing an additional ε to the multiplicative stretch. We further view this result in a broader framework of ((3𝓁+4)/(𝓁+2) + ε)-APASP algorithms, similarly to the family of (3𝓁+4)/(𝓁+2)-APASP algorithms by Akav and Roditty [ESA'21]. This also generalizes the (2+ε)-APASP algorithm by Dory, Forster, Kirkpatrick, Nazari, Vassilevska Williams, and de Vos [SODA'24]. Finally, we show that it is possible to "bypass" an Ω̃ (n^ω) conditional lower bound by Dor, Halperin, and Zwick for α-APASP with α < 2, by allowing an additive component to the approximation (e.g. a ((6k+3)/(3k+2),∑_{i=1}^{k+1} W_i)-APASP with Õ(n^{2+1/(3k+2)}) runtime.).

In this paper, we study the problem of compact routing schemes in weighted undirected and directed graphs. For weighted undirected graphs, more than a decade ago, Chechik [PODC'13] presented a ≈ 3.68k-stretch compact routing scheme that uses Õ(n^{1/k}log{D}) local storage, where D is the normalized diameter, for every k > 1. We present a ≈ 2.64k-stretch compact routing scheme that uses Õ(n^{1/k}) local storage on average in each vertex. This is the first compact routing scheme that uses total local storage of Õ(n^{1+1/k}) while achieving a c ⋅ k stretch, for a constant c < 3. In real-world network protocols, messages are usually transmitted as part of a communication session between two parties. Therefore, more than two decades ago, Thorup and Zwick [SPAA'01] considered compact routing schemes that establish a communication session using a handshake. In their handshake-based compact routing scheme, the handshake is routed along a (4k-5)-stretch path, and the rest of the communication session is routed along an optimal (2k-1)-stretch path. It is straightforward to improve the (4k-5)-stretch of the handshake to ≈ 3.68k-stretch using the compact routing scheme of Chechik [PODC'13]. We improve the handshake stretch to the optimal (2k-1), by borrowing the concept of roundtrip routing from directed graphs to undirected graphs. For weighted directed graphs, more than two decades ago, Roditty, Thorup, and Zwick [SODA'02 and TALG'08] presented a (4k+ε)-stretch compact roundtrip routing scheme that uses Õ(n^{1/k}) local storage for every k ≥ 3. For k = 3, this gives a (12+ε)-roundtrip stretch using Õ(n^{1/3}) local storage. We improve the stretch by developing a 7-roundtrip stretch routing scheme with Õ(n^{1/3}) local storage. In addition, we consider graphs with bounded hop diameter and present an optimal (2k-1)-roundtrip stretch routing scheme that uses Õ(D_{HOP}⋅ n^{1/k}), where D_{HOP} is the hop diameter of the graph.

In many settings, there is an organizer who would like to divide a set of agents into k coalitions, and cares about the friendships within each coalition. Specifically, the organizer might want to maximize utilitarian social welfare, maximize egalitarian social welfare, or simply guarantee that every agent will have at least one friend within his coalition. However, in many situations, the organizer is not familiar with the friendship connections, and he needs to obtain them from the agents. In this setting, a manipulative agent may falsely report friendship connections in order to increase his utility. In this paper, we analyze the complexity of finding manipulation in such k-coalitional games on graphs. We also introduce a new type of manipulation, socially-aware manipulation, in which the manipulator would like to increase his utility without decreasing the social welfare. We then study the complexity of finding socially-aware manipulation in our setting. Finally, we examine the frequency of socially-aware manipulation and the running time of our algorithms via simulation results.

For an undirected unweighted graph G = (V,E) with n vertices and m edges, let d(u,v) denote the distance from u ∈ V to v ∈ V in G. An (α,β)-stretch approximate distance oracle (ADO) for G is a data structure that given u,v ∈ V returns in constant (or near constant) time a value dˆ(u,v) such that d(u,v) ≤ dˆ(u,v) ≤ α⋅ d(u,v) + β, for some reals α > 1, β. Thorup and Zwick [Mikkel Thorup and Uri Zwick, 2005] showed that one cannot beat stretch 3 with subquadratic space (in terms of n) for general graphs. Pǎtraşcu and Roditty [Mihai Pǎtraşcu and Liam Roditty, 2010] showed that one can obtain stretch 2 using O(m^{1/3}n^{4/3}) space, and so if m is subquadratic in n then the space usage is also subquadratic. Moreover, Pǎtraşcu and Roditty [Mihai Pǎtraşcu and Liam Roditty, 2010] showed that one cannot beat stretch 2 with subquadratic space even for graphs where m = Õ(n), based on the set-intersection hypothesis. In this paper we explore the conditions for which an ADO can beat stretch 2 while using subquadratic space. In particular, we show that if the maximum degree in G is Δ_G ≤ O(n^{1/k-ε}) for some 0 < ε ≤ 1/k, then there exists an ADO for G that uses Õ(n^{2-(kε)/3) space and has a (2,1-k)-stretch. For k = 2 this result implies a subquadratic sub-2 stretch ADO for graphs with Δ_G ≤ O(n^{1/2-ε}). Moreover, we prove a conditional lower bound, based on the set intersection hypothesis, which states that for any positive integer k ≤ log n, obtaining a sub-(k+2)/k stretch for graphs with Δ_G = Θ(n^{1/k}) requires Ω̃(n²) space. Thus, for graphs with maximum degree Θ(n^{1/2}), obtaining a sub-2 stretch requires Ω̃(n²) space.

Abstract Let $$S \subseteq \mathbb {R}^2$$ S ⊆ R 2 be a set of nsites in the plane, so that every site $$s \in S$$ s ∈ S has an associated radius $$r_s > 0$$ r s > 0 . Let $$\mathcal {D}(S)$$ D ( S ) be the disk intersection graph defined by S, i.e., the graph with vertex set S and an edge between two distinct sites $$s, t \in S$$ s , t ∈ S if and only if the disks with centers s, t and radii $$r_s$$ r s , $$r_t$$ r t intersect. Our goal is to design data structures that maintain the connectivity structure of $$\mathcal {D}(S)$$ D ( S ) as sites are inserted and/or deleted in S. First, we consider unit disk graphs, i.e., we fix $$r_s = 1$$ r s = 1 , for all sites $$s \in S$$ s ∈ S . For this case, we describe a data structure that has $$O(\log ^2 n)$$ O ( log 2 n ) amortized update time and $$O(\log n/\log \log n)$$ O ( log n / log log n ) query time. Second, we look at disk graphs with bounded radius ratio $$\Psi $$ Ψ , i.e., for all $$s \in S$$ s ∈ S , we have $$1 \le r_s \le \Psi $$ 1 ≤ r s ≤ Ψ , for a parameter $$\Psi $$ Ψ that is known in advance. Here, we not only investigate the fully dynamic case, but also the incremental and the decremental scenario, where only insertions or only deletions of sites are allowed. In the fully dynamic case, we achieve amortized expected update time $$O(\Psi \log ^{4} n)$$ O ( Ψ log 4 n ) and query time $$O(\log n/\log \log n)$$ O ( log n / log log n ) . This improves the currently best update time by a factor of $$\Psi $$ Ψ . In the incremental case, we achieve logarithmic dependency on $$\Psi $$

Abstract. Let [Formula: see text] be an [Formula: see text]-node [Formula: see text]-edge weighted undirected graph, where [Formula: see text] is a real length function defined on its edges, and let [Formula: see text] denote the girth of [Formula: see text], i.e., the length of a shortest cycle. We present an algorithm that, for any input, integer [Formula: see text], in [Formula: see text] expected time finds a cycle of length at most [Formula: see text]. This algorithm nearly matches an [Formula: see text]-time algorithm of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492] which applied to unweighted graphs of girth 3. For weighted graphs, this result also improves upon the previous state-of-the-art algorithm that in [Formula: see text] time, where [Formula: see text] is an integral length function, finds a cycle of length at most [Formula: see text] of Kadria et al. [ Algorithmic trade-offs for girth approximation in undirected graphs, in Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2022, pp. 1471–1492]. For [Formula: see text], this result improves upon the result of Roditty and Tov [ ACM Trans. Algorithms, 9 (2013), pp. 15:1–15:13].

Let G=(V,E) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an (min{n3/2m1/2,n7/3 })-time algorithm that computes estimated distances with an additive approximation of 2 without using Fast Matrix Multiplication (FMM). Recently, Deng, Kirkpatrick, Rong, V. Williams and Zhong [ICALP 2022] improved the running time for dense graphs to (n2.29)-time, using FMM, where an exact solution can be computed with FMM in (nω) time (ω < 2.37286) using Seidel’s algorithm.

We present several new efficient algorithms for approximating the girth, g, of weighted and unweighted n-vertex, m-edge undirected graphs. For undirected graphs with polynomially bounded, integer, non-negative edge weights, we provide an algorithm that for every integer k ≥ 1, runs in Õ(m + n1 + 1/k log g) time and returns a cycle of length at most 2kg. For unweighted, undirected graphs we present an algorithm that for every k ≥ 1, runs in Õ(n1 + 1/k) time and returns a cycle of length at most 2k[g/2], an almost k-approximation. Both algorithms provide trade-offs between the running time and the quality of the approximation. We also obtain faster algorithms for approximation factors better than 2, and improved approximations when the girth is odd or small (e.g., 3 and 4).

Let G = (V,E) be a weighted undirected graph with n vertices and m edges, and let d_G(u,v) be the length of the shortest path between u and v in G. In this paper we present a unified approach for obtaining algorithms for all pairs approximate shortest paths in weighted undirected graphs. For every integer k ≥ 2 we show that there is an Õ(n²+kn^{2-3/k}m^{2/k}) expected running time algorithm that computes a matrix M such that for every u,v ∈ V: d_G(u,v) ≤ M[u,v] ≤ (2+(k-2)/k)d_G(u,v). Previous algorithms obtained only specific approximation factors. Baswana and Kavitha [FOCS 2006, SICOMP 2010] presented a 2-approximation algorithm with expected running time of Õ(n²+m√ n) and a 7/3-approximation algorithm with expected running time of Õ(n²+m^{2/3}n). Their results improved upon the results of Cohen and Zwick [SODA 1997, JoA 2001] for graphs with m = o(n²). Kavitha [FSTTCS 2007, Algorithmica 2012] presented a 5/2-approximation algorithm with expected running time of Õ(n^{9/4}). For k = 2 and k = 3 our result gives the algorithms of Baswana and Kavitha. For k = 4, we get a 5/2-approximation algorithm with Õ(n^{5/4}m^{1/2}) expected running time. This improves upon the running time of Õ(n^{9/4}) due to Kavitha, when m = o(n²). Our unified approach reveals that all previous algorithms are a part of a family of algorithms that exhibit a smooth tradeoff between approximation of 2 and 3, and are not sporadic unrelated results. Moreover, our new algorithm uses, among other ideas, the celebrated approximate distance oracles of Thorup and Zwick [STOC 2001, JACM 2005] in a non standard way, which we believe is of independent interest, due to their extensive usage in a variety of applications.

Among the most important graph parameters is the diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. [ Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041--1052] showed that the diameter can be approximated within a multiplicative factor of 3/2 in $\tilde{O}(m^{3/2})$ time. Furthermore, Roditty and Vassilevska W. [ Proceedings of STOC '13, New York, ACM, 2013, pp. 515--524] showed that unless the strong exponential time hypothesis (SETH) fails, no $O(n^{2-{\varepsilon}})$ time algorithm can achieve an approximation factor better than 3/2 in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than 3/2. It was, however, completely plausible that a 3/2-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no $O(m^{3/2-{\varepsilon}})$ time algorithm can achieve an approximation factor better than 5/3. Another fundamental set of graph parameters is the eccentricities. The eccentricity of a vertex $v$ is the distance between $v$ and the farthest vertex from $v$. Chechik et al. [ Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041--1052] showed that the eccentricities of all vertices can be approximated within a factor of $5/3$ in $\tilde{O}(m^{3/2})$ time and Abboud, Vassilevska W., and Wang [ Proceedings of SODA 2016, Arlington, VA, 2016, pp. 377--391] showed that no $O(n^{2-{\varepsilon}})$ algorithm can achieve better than 5/3 approximation in sparse graphs. We show that the runtime of the 5/3 approximation algorithm is also optimal by proving that under SETH, there is no $O(m^{3/2-{\varepsilon}})$ algorithm that achieves a better than 9/5 approximation. We also show that no near-linear time algorithm can achieve a better than 2 approximation for the eccentricities. This is the first lower bound in fine-grained complexity that addresses near-linear time computation. We show that our lower bound for near-linear time algorithms is essentially tight by giving an algorithm that approximates eccentricities within a $2+\delta$ factor in $\tilde{O}(m/\delta)$ time for any $0<\delta<1$. This beats all eccentricity algorithms in Cairo, Grossi, and Rizzi [ Proceedings of SODA 2016, Arlington, VA, 2016, pp. 363--376] and is the first constant factor approximation for eccentricities in directed graphs. To establish the above lower bounds we study the $S$-$T$ diameter problem: Given a graph and two subsets $S$ and $T$ of vertices, output the largest distance between a vertex in $S$ and a vertex in $T$. We give new algorithms and show tight lower bounds that serve as a starting point for all other hardness results. Our lower bounds apply only to sparse graphs. We show that for dense graphs, there are near-linear time algorithms for $S$-$T$ diameter, diameter, and eccentricities, with almost the same approximation guarantees as their $\tilde{O}(m^{3/2})$ counterparts, improving upon the best known algorithms for dense graphs.

Let G = (V, E) be an unweighted undirected graph with n vertices and m edges. Dor, Halperin, and Zwick [FOCS 1996, SICOMP 2000] presented an Õ(n2)-time algorithm that computes estimated distances with a multiplicative approximation of 3. Berman and Kasiviswanathan [WADS 2007] improved the approximation of Dor et al. and presented an Õ(n2)-time algorithm that produces for every u, v ϵ V an estimate (u, v) such that: dG(u, v) ≤ (u, v) ≤ 2dG(u, v) + 1. We refer to such an approximation as an (α, β)-approximation, where a is the multiplicative approximation and β is the additive approximation. A prerequisite for an O(n2−ε)-time algorithm, where ε ϵ (0, 1), is a data structure that uses O(n2−δ) space, for some δ ≥ ε, and answers queries in constant time. An O(n2−ε)-time (3, 0)-approximation algorithm became plausible after Thorup and Zwick [STOC 2001, JACM 2005] presented their approximate distance oracles, and in particular an O(n1.5)-space data structure that reports a (3, 0)-approximate distance in O(1) time. Indeed, using Thorup and Zwick distance oracles together with more ideas, Baswana, Gaur, Sen, and Upadhyay [ICALP 2008] improved the running time of Dor et al., and obtained an O(n2−ε) time algorithm, at the cost of introducing also an additive approximation. They presented an algorithm that in Õ(m + n23/12) expected running time constructs an O(n1.5)-space data structure, that in O(1) time reports a (3, 14)-approximate distance. An O(n2−ε)-time (2, 1)-approximation algorithm became plausible only after Pǎtraşcu and Roditty [FOCS 2010, SICOMP 2014] presented an O(n5/3)-space data structure that reports (2, 1)-approximate distances in O(1) time. However, only few years ago, Sommer [ICALP 2016] obtained an Õ(n2) time algorithm that computes a (2, 1)-distance oracle with Õ(n5/3) space. This leads to the following natural question of whether Ω(n2) time is a lower bound for any (3−α, β)-approximation, where α ϵ (0, 1), and β is constant. In this paper we show that this is not the case by presenting an algorithm that for every ε ϵ (0, 1/2) computes in Õ(m) + n2−Ω(ε) time an -space data structure that in O(1/ε) time reports, for every u, v ϵ V, an estimate (u, v) such that: Our result improves, simultaneously, the running time and the multiplicative approximation of the Õ(n2)-time (3, 0)-approximation algorithm of Dor et al. at the cost of introducing also an additive approximation.

Abstract We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $$L_p$$ L p -norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $$O(n \log ^3 n)$$ O ( n log 3 n ) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required $$O(n^{\varepsilon })$$ O ( n ε ) time for an update and $$O(\log n)$$ O ( log n ) time for a query [SICOMP 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $$O(n^{\varepsilon })$$ O ( n ε ) factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan’s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in $${{\mathbb {R}}}^3$$ R 3 . Along the way, we also revisit Chan’s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).

Let G=(V,E) be an n -vertices m -edges directed graph with edge weights in the range [1, W ] for some parameter W , and sϵ V be a designated source. In this article, we address several variants of the problem of maintaining the (1+ε)-approximate shortest path from s to each v ϵ V { s } in the presence of a failure of an edge or a vertex. From the graph theory perspective, we show that G has a subgraph H with Õ(ε -1 } n log W ) edges such that for any x,vϵ V , the graph H \ x contains a path whose length is a (1+ε)-approximation of the length of the shortest path from s to v in G \ x . We show that the size of the subgraph H is optimal (up to logarithmic factors) by proving a lower bound of Ω (ε -1 n log W ) edges. Demetrescu, Thorup, Chowdhury, and Ramachandran (SICOMP 2008) showed that the size of a fault tolerant exact shortest path subgraph in weighted directed/undirected graphs is Ω ( m ). Parter and Peleg (ESA 2013) showed that even in the restricted case of unweighted undirected graphs, the size of any subgraph for the exact shortest path is at least Ω ( n 1.5 ). Therefore, a (1+ε)-approximation is the best one can hope for. We consider also the data structure problem and show that there exists an ϕ(ε -1 n log W ) size oracle that for any vϵ V reports a (1+ε)-approximate distance of v from s on a failure of any xϵ V in O(log log 1+ε ( nW )) time. We show that the size of the oracle is optimal (up to logarithmic factors) by proving a lower bound of Ω (ε -1 n log W log -1 n ). Finally, we present two distributed algorithms . We present a single-source routing scheme that can route on a (1+ε)-approximation of the shortest path from a fixed source s to any destination t in the presence of a fault. Each vertex has a label and a routing table of ϕ(ε -1 log W ) bits. We present also a labeling scheme that assigns each vertex a label of ϕ(ε -1 log W ) bits. For any two vertices x,vϵ V , the labeling scheme outputs a (1+ε)-approximation of the distance from s to v in G \ x using only the labels of x and v .

Let $S \subset \mathbb{R}^2$ be a set of $n$ sites, where each $s \in S$ has an associated radius $r_s > 0$. The disk graph $D(S)$ is the undirected graph with vertex set $S$ and an undirected edge between two sites $s, t \in S$ if and only if $|st| \leq r_s + r_t$, i.e., if the disks with centers $s$ and $t$ and respective radii $r_s$ and $r_t$ intersect. Disk graphs are used to model sensor networks. Similarly, the transmission graph $T(S)$ is the directed graph with vertex set $S$ and a directed edge from a site $s$ to a site $t$ if and only if $|st| \leq r_s$, i.e., if $t$ lies in the disk with center $s$ and radius $r_s$. We provide algorithms for detecting (directed) triangles and, more generally, computing the length of a shortest cycle (the girth) in $D(S)$ and in $T(S)$. These problems are notoriously hard in general, but better solutions exist for special graph classes such as planar graphs. We obtain similarly efficient results for disk graphs and for transmission graphs. More precisely, we show that a shortest (Euclidean) triangle in $D(S)$ and in $T(S)$ can be found in $O(n \log n)$ expected time, and that the (weighted) girth of $D(S)$ can be found in $O(n \log n)$ expected time. For this, we develop new tools for batched range searching that may be of independent interest.

The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the ones that follow from trivial recomputation after each update or from solving dynamic All-Pairs Shortest Paths (APSP), which is very computationally intensive. This is the situation for dynamic approximation algorithms as well, and even if only edge insertions or edge deletions need to be supported. This paper provides a comprehensive study of the dynamic approximation of Diameter, Radius and Eccentricities, providing both conditional lower bounds, and new algorithms whose bounds are optimal under popular hypotheses in fine-grained complexity. Some of the highlights include: - Under popular hardness hypotheses, there can be no significantly better fully dynamic approximation algorithms than recomputing the answer after each update, or maintaining full APSP. - Nearly optimal partially dynamic (incremental/decremental) algorithms can be achieved via efficient reductions to (incremental/decremental) maintenance of Single-Source Shortest Paths. For instance, a nearly $(3/2+ε)$-approximation to Diameter in directed or undirected graphs can be maintained decrementally in total time $m^{1+o(1)}\sqrt{n}/ε^2$. This nearly matches the static $3/2$-approximation algorithm for the problem that is known to be conditionally optimal.

Suppose we are given a set D of n pairwise intersecting disks in the plane. A planar point set P stabs D if and only if each disk in D contains at least one point from P. We present a deterministic algorithm that takes O(n) time to find five points that stab D. Furthermore, we give a simple example of 13 pairwise intersecting disks that cannot be stabbed by three points. This provides a simple - albeit slightly weaker - algorithmic version of a classical result by Danzer that such a set D can always be stabbed by four points.

Let G = (V, E) be an n-vertices m-edges directed graph with edge weights in the range [1, W] and L = log(W). Let s ∊ V be a designated source. In this paper we address several variants of the problem of maintaining the (1 + ∊)-approximate shortest path from s to each υ ∊ V \ {s} in the presence of a failure of an edge or a vertex. From the graph theory perspective we show that G has a subgraph H with Õ(nL/∊) edges such that for any x,υ ∊ V, the graph H \ x contains a path whose length is a (1 + ∊)-approximation of the length of the shortest path from s to υ in G \ x. We show that the size of the subgraph H is optimal (up to logarithmic factors) by proving a lower bound of Ω(nL/∊) edges. Demetrescu, Thorup, Chowdhury and Ramachandran [12] showed that the size of a fault tolerant exact shortest path subgraph in weighted directed/undirected graphs is Ω(m). Parter and Peleg [18] showed that even in the restricted case of unweighted undirected graphs the size of any subgraph for the exact shortest path is at least Ω(n1.5). Therefore, a (1 + ∊)-approximation is the best one can hope for. We consider also the data structure problem and show that there exists an Õ(nL/∊) size oracle that for any υ ∊ V reports a (1 + ∊)-approximate distance of v from s on a failure of any x ∊ V in O(loglog1+∊(nW)) time. We show that the size of the oracle is optimal (up to logarithmic factors) by proving a lower bound of Ω(nL/∊ log n). Finally, we present two distributed algorithms. We present a single source routing scheme that can route on a (1 + ∊)-approximation of the shortest path from a fixed source s to any destination t in the presence of a fault. Each vertex has a label and a routing table of Õ(L/∊) bits. We present also a labeling scheme that assigns each vertex a label of Õ(L/∊) bits. For any two vertices x, υ ∊ V the labeling scheme outputs a (1 + ∊)-approximation of the distance from s to υ in G\x using only the labels of x and v.

The girth of a graph, i.e. the length of its shortest cycle, is a fundamental graph parameter. Unfortunately all known algorithms for computing, even approximately, the girth and girth-related structures in directed weighted m-edge and n-node graphs require Ω(min{nω, mn}) time (for 2 ≤ ω < 2.373). In this paper, we drastically improve these runtimes as follows: • Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in Õ(m) time computes an Õ(1)-multiplicative approximation of the girth as well as an Õ(1)-multiplicative roundtrip spanner with Õ(n) edges with high probability (w.h.p). • Nearly Tight Additive Approximations: For unweighted graphs and any a ∊ (0, 1) we give an algorithm that in Õ(mn1–a) time computes an O(na)-additive approximation of the girth, w.h.p. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial boolean matrix multiplication. We also show that if the girth is O(na), then the same guarantee can be achieved via a deterministic algorithm. Our main technical contribution to achieve these results is the first nearly linear time algorithm for computing roundtrip covers, a directed graph decomposition concept key to previous roundtrip spanner constructions. Previously it was not known how to compute these significantly faster than Ω(mn) time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.

Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. [SODA 2014] showed that the diameter can be approximated within a multiplicative factor of 3/2 in Õ(m3/2) time. Furthermore, Roditty and Vassilevska W. [STOC 13] showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no O(n2−ε) time algorithm can achieve an approximation factor better than 3/2 in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than 3/2. It was, however, completely plausible that a 3/2-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no O(m3/2−ε) time algorithm can achieve an approximation factor better than 5/3.

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and a designated source vertex $s$. We address the problem of single-source reachability (SSR) from $s$ in the presence of failures of vertices/edges. We show that for every $k\geq1$, there is a subgraph $H$ of $G$ with at most $2^kn$ edges that preserves the reachability from $s$ even after the failure of any $k$ edges. Formally, given a set $F$ of $k$ edges, a vertex $v\in V(G)$ is reachable from $s$ in $G\setminus F$ if and only if $v$ is reachable from $s$ in $H\setminus F$. We call $H$ a $k$-fault tolerant reachability subgraph ($\textsc{$k$-FTRS}$). We also prove a matching lower bound of $\Omega(2^kn)$ edges for such subgraphs that holds for all $n,k$ with $2^k\leq n$. Our results extend to vertex failures without any extra overhead. The construction of ${$k$-FTRS}$ is interesting from several different perspectives. From the Graph theory perspective it reveals a separation between SSR and single-source shortest paths (SSSP) in directed graphs. More specifically, in the case of SSSP in weighted directed and undirected graphs, Demetrescu et al. showed that there is a lower bound of $\Omega(m)$ edges even for a single edge failure [ SIAM J. Comput., 37 (2008), pp. 1299--1318]. In the case of unweighted graphs Parter and Peleg gave a lower bound of $\Omega(n^{3/2})$ edges, again, even for a single edge failure [ Proc. Algorithms---21st Annual European Symposium, 2013, pp. 779--790]. From the Algorithms perspective it implies fault-tolerant algorithms for other interesting problems, namely, (i) verifying if the strong connectivity of a graph is preserved after $k$ edge or vertex failures, and (ii) computing a dominator tree of a graph after $k$-failures. From the perspective of techniques it makes an interesting usage of the concept of farthest min-cut which was already introduced by Ford and Fulkerson in their pioneering work on flows and cuts [ Flows in Networks, Princeton University Press, 1962; reprinted 2011]. We show that there is a close relationship between the farthest min-cut and the ${$k$-FTRS}$. We believe that our new technique is of independent interest.

Let $P \subset \mathbb{R}^2$ be a planar $n$-point set such that each point $p \in P$ has an associated radius $r_p > 0$. The transmission graph $G$ for $P$ is the directed graph with vertex set $P$ such that for any $p, q \in P$, there is an edge from $p$ to $q$ if and only if $d(p, q) \leq r_p$. Let $t > 1$ be a constant. A $t$-spanner for $G$ is a subgraph $H \subseteq G$ with vertex set $P$ so that for any two vertices $p,q \in P$, we have $d_H(p, q) \leq t d_G(p, q)$, where $d_H$ and $d_G$ denote the shortest path distance in $H$ and $G$, respectively (with Euclidean edge lengths). We show how to compute a $t$-spanner for $G$ with $O(n)$ edges in $O(n (\log n + \log \Psi))$ time, where $\Psi$ is the ratio of the largest and smallest radius of a point in $P$. Using more advanced data structures, we obtain a construction that runs in $O(n \log^5 n)$ time, independent of $\Psi$. We give two applications for our spanners. First, we show how to use our spanner to find a BFS tree in $G$ from any given start vertex in $O(n \log n)$ time (in addition to the time it takes to build the spanner). Second, we show how to use our spanner to extend a reachability oracle to answer geometric reachability queries. In a geometric reachability query we ask whether a vertex $p$ in $G$ can “reach” a target $q$ which is an arbitrary point in the plane (rather than restricted to be another vertex $q$ of $G$ in a standard reachability query). Our spanner allows the reachability oracle to answer geometric reachability queries with an additive overhead of $O(\log n\log \Psi)$ to the query time and $O(n \log \Psi)$ to the space.

In this paper we study the problem of maintaining the strongly connected components of a graph in the presence of failures. In particular, we show that given a directed graph G=(V,E) with n=|V| and m=|E|, and an integer value k\geq 1, there is an algorithm that computes in O(2^{k}n log^2 n) time for any set F of size at most k the strongly connected components of the graph G\F. The running time of our algorithm is almost optimal since the time for outputting the SCCs of G\F is at least \Omega(n). The algorithm uses a data structure that is computed in a preprocessing phase in polynomial time and is of size O(2^{k} n^2). Our result is obtained using a new observation on the relation between strongly connected components (SCCs) and reachability. More specifically, one of the main building blocks in our result is a restricted variant of the problem in which we only compute strongly connected components that intersect a certain path. Restricting our attention to a path allows us to implicitly compute reachability between the path vertices and the rest of the graph in time that depends logarithmically rather than linearly in the size of the path. This new observation alone, however, is not enough, since we need to find an efficient way to represent the strongly connected components using paths. For this purpose we use a mixture of old and classical techniques such as the heavy path decomposition of Sleator and Tarjan and the classical Depth-First-Search algorithm. Although, these are by now standard techniques, we are not aware of any usage of them in the context of dynamic maintenance of SCCs. Therefore, we expect that our new insights and mixture of new and old techniques will be of independent interest.

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions that includes Lp-norms and additively weighted Euclidean distances, and for general (convex, pair- wise disjoint) sites that have constant description complexity (line segments, disks, etc.). Our data structure has a polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required O(n∊) time for an update and O(log n) time for a query [1]. Our data structure has numerous applications, and in all of them it gives faster algorithms, typically reducing an O(n∊) factor in the bounds to polylogarithmic. To further demonstrate its effectiveness, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph. To obtain this data structure, we combine and extend various techniques and obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for finding the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest- neighbor context). To analyze this algorithm, we improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we plug our vertical shallow cutting construction into Chan's algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in ℝ3. While doing this, we also revisit Chan's technique and present a variant that uses a single binary counter, with a simpler analysis and an improved amortized deletion time.

Let G=(V,E) be an n-vertices m-edges directed graph. Let s∈ V be any designated source vertex. We address the problem of single source reachability (SSR) from s in presence of failures of vertices/edges. We show that for every k≥ 1, there is a subgraph H of G with at most 2k n edges that preserves the reachability from s even after the failure of any k edges. Formally, given a set F of k edges, a vertex u∈ V is reachable from s in G∖ F if and only if u is reachable from s in H∖ F. We call H a k-Fault Tolerant Reachability Subgraph (k-FTRS). We prove also a matching lower bound of Ω(2kn) for such subgraphs. Our results extend to vertex failures without any extra overhead. The general construction of k-FTRS is interesting from several different perspectives. From the Graph theory perspective it reveals a separation between SSR and single source shortest paths (SSSP) in directed graphs. More specifically, in the case of SSSP in weighted directed graphs, there is a lower bound of Ω(m) even for a single edge failure. In the case of unweighted graphs there is a lower bound of Ω(n3/2) edges, again, even for a single edge failure. There is also a matching upper bound but nothing is known for two or more failures in the directed graphs. From the Algorithms perspective it implies fault tolerant solutions to other interesting problems, namely, (i) verifying if the strong connectivity of a graph is preserved after k edge or vertex failures, (ii) computing a dominator tree of a graph after k-failures. From the perspective of Techniques it makes an interesting usage of the concept of farthest min-cut which was already introduced by Ford and Fulkerson in their pioneering work on flows and cuts. We show that there is a close relationship between the farthest min-cut and the k-FTRS. We believe that our new technique is of independent interest.

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of $O(m+n\log n)$ and a worst-case query time of $O(n)$, where $m$ is the current number of edges in the graph, and $n$ is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting ``retrospectiveness'' property. Each insert operation creates a new version of the graph. A delete operation deletes edges from all versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in $O(m\alpha(n))$ amortized time, and each query in $O(1)$ worst-case time, where $\alpha(n)$ is a functional inverse of Ackermann's function appearing in the analysis of the Union-Find data structure. Note that the update time of $O(m\alpha(n))$, in the case of a delete operation, is the time needed for updating all versions of the graph.

Let P be a set of n points in d dimensions, each with an associated radius r_p > 0. The transmission graph G for P has vertex set P and an edge from p to q if and only if q lies in the ball with radius r_p around p. Let t > 1. A t-spanner H for G is a sparse subgraph of G such that for any two vertices p, q connected by a path of length l in G, there is a p-q-path of length at most tl in H. We show how to compute a t-spanner for G if d=2. The running time is O(n (log n + log Psi)), where Psi is the ratio of the largest and smallest radius of two points in P. We extend this construction to be independent of Psi at the expense of a polylogarithmic overhead in the running time. As a first application, we prove a property of the t-spanner that allows us to find a BFS tree in G for any given start vertex s of P in the same time. After that, we deal with reachability oracles for G. These are data structures that answer reachability queries: given two vertices, is there a directed path between them? The quality of a reachability oracle is measured by the space S(n), the query time Q(n), and the preproccesing time. For d=1, we show how to compute an oracle with Q(n) = O(1) and S(n) = O(n) in time O(n log n). For d=2, the radius ratio Psi again turns out to be an important measure for the complexity of the problem. We present three different data structures whose quality depends on Psi: (i) if Psi < sqrt(3), we achieve Q(n) = O(1) with S(n) = O(n) and preproccesing time O(n log n); (ii) if Psi >= sqrt(3), we get Q(n) = O(Psi^3 sqrt(n)) and S(n) = O(Psi^5 n^(3/2)); and (iii) if Psi is polynomially bounded in n, we use probabilistic methods to obtain an oracle with Q(n) = O(n^(2/3)log n) and S(n) = O(n^(5/3) log n) that answers queries correctly with high probability. We employ our t-spanner to achieve a fast preproccesing time of O(Psi^5 n^(3/2)) and O(n^(5/3) log^2 n) in case (ii) and (iii), respectively.

In this paper we present two new routing techniques that allow us to obtain the following new routing schemes: A routing scheme for n-nodes, m-edges unweighted graphs that uses Õ(1/ε n2/3) space at each vertex and Õ(1/ε)-bit headers, to route a message between any pair of vertices u,v ∈ V on a (2 + ε,1)-stretch path, i.e., a path of length at most (2 + ε)• d+1, where d is the distance between u and v. This should be compared to the (2,1)-stretch and Õ(n5/3) space distance oracle of patrascu and Roditty [FOCS'10 and SIAM J. Comput. 2014] and to the (2,1)-stretch routing scheme of Abraham and Gavoille [DISC'11] that uses Õ(n3/4) space at each vertex. It follows from patrascu, Thorup and Roditty [FOCS'12] that a 2-stretch distance oracle with Õ(m2/3) space at each vertex is optimal, assuming a hardness conjecture on set intersection holds. A routing scheme for n-nodes weighted graphs with normalized diameter D, that uses Õ(1/ε n1/3log D) space at each vertex and Õ(1/ε log D)-bit headers, to route a message between any pair of vertices on a (5+ε)-stretch path. This should be compared to the 5-stretch and Õ(n4/3) space distance oracle of Thorup and Zwick [STOC'01 and J. ACM. 2005] and to the 7-stretch routing scheme of Thorup and Zwick [SPAA'01] that uses Õ(n1/3) space at each vertex. Since a 5-stretch routing scheme must use tables of Ω(n1/3) space our result is almost tight. For an integer l>1, a routing scheme for n-nodes unweighted graphs that uses Õ(l 1/ε nl/(2 l pm 1)) space at each vertex and O(1/ε)-bit headers, to route a message between any pair of vertices on a (3 pm 2 / l + ε,2)-stretch path. This should be compared to the distance oracles of patrascu, Thorup and Roditty [FOCS'12] for weighted graphs with a stretch of (3 pm 2/l) and Õ(l m1+l/(2 l pm 1)) total space. A routing scheme for n-nodes weighted graphs, that for any integer k>2, uses Õ(1/ε n1/klog D) space at each vertex and Õ(1/ε log D)-bit headers, to route a message between any pair of vertices on a (4k-7+ε)-stretch path. This improves the (4k-5)-stretch routing scheme of Thorup and Zwick [SPAA'01] and can also be used in the recent ((4 - α)k - β)-stretch routing scheme of Chechik [PODC'13] to obtain slightly better values for α and β.

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

We give the first improvement to the space/approximation trade-off of distance oracles since the seminal result of Thorup and Zwick. For unweighted undirected graphs, our distance oracle has size $O(n^{5/3})$ and, when queried about vertices at distance $d$, returns a path of length at most 2d+1. For weighted undirected graphs with $m=n^2/\alpha$ edges, our distance oracle has size $O(n^2 / \sqrt[3]{\alpha})$ and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space $\widetilde{\Omega}(n^2 / \sqrt{\alpha})$. For unweighted graphs, this implies a $\widetilde{\Omega}(n^{1.5})$ space lower bound to achieve approximation 2d+1.

We consider the problem of maintaining the strongly connected components (SCCs) of an n-nodes and m-edges directed graph that undergoes a sequence of edge deletions. Recently, in SODA 2011, Łącki presented a deterministic algorithm that preprocess the graph in O(mn) time and creates a data structure that maintains the SCCs of a graph under edge deletions with a total update time of O(mn). The data structure answers strong connectivity queries in O(1) time. The worst case update time after a single edge deletion might be as large as O(mn). In this paper we reduce the preprocessing time and the worst case update time of Łącki's data structure from O(mn) to O(m log n). The query time and the total update time remain unchanged.

The diameter and the radius of a graph are fundamental topological parameters that have many important practical applications in real world networks. The fastest combinatorial algorithm for both parameters works by solving the all-pairs shortest paths problem (APSP) and has a running time of ~O(mn) in m-edge, n-node graphs. In a seminal paper, Aingworth, Chekuri, Indyk and Motwani [SODA'96 and SICOMP'99] presented an algorithm that computes in ~O(m√ n + n2) time an estimate D for the diameter D, such that ⌊ 2/3 D ⌋ ≤ ^D ≤ D. Their paper spawned a long line of research on approximate APSP. For the specific problem of diameter approximation, however, no improvement has been achieved in over 15 years.

This article considers the problem of computing a minimum weight cycle in weighted undirected graphs. Given a weighted undirected graph G = ( V , E , w ), let C be a minimum weight cycle of G , let w ( C ) be the weight of C , and let w max ( C ) be the weight of the maximum edge of C . We obtain three new approximation algorithms for the minimum weight cycle problem: (1) for integral weights from the range [1, M ], an algorithm that reports a cycle of weight at most 4 3 w ( C ) in O ( n 2 log n (log n + log M )) time; (2) For integral weights from the range [1, M ], an algorithm that reports a cycle of weight at most w ( C ) + w max ( C ) in O ( n 2 log n (log n + log M )) time; (3) For nonnegative real edge weights, an algorithm that for any ε > 0 reports a cycle of weight at most (4 3 + ε ) w ( C ) in O (1 ε n 2 log n (log log n )) time. In a recent breakthrough, Williams and Williams [2010] showed that a subcubic algorithm, that computes the exact minimum weight cycle in undirected graphs with integral weights from the range [1, M ], implies a subcubic algorithm for computing all-pairs shortest paths in directed graphs with integral weights from the range [− M , M ]. This implies that in order to get a subcubic algorithm for computing a minimum weight cycle, we have to relax the problem and to consider an approximated solution. Lingas and Lundell [2009] were the first to consider approximation in the context of minimum weight cycle in weighted graphs. They presented a 2-approximation algorithm for integral weights with O ( n 2 log n (log n + log M )) running time. They also posed, as an open problem, the question whether it is possible to obtain a subcubic algorithm with a c -approximation, where c < 2. The current article answers this question in the affirmative, by presenting an algorithm with 4/3-approximation and the same running time. Surprisingly, the approximation factor of 4/3 is not accidental. We show, using the new result of Williams and Williams [2010], that a subcubic combinatorial algorithm with (4/3 − ε )-approximation, where 0 < ε ≤ 1/3, implies a subcubic combinatorial algorithm for multiplying two boolean matrices.

Given a weighted undirected graph, our basic goal is to represent all pairwise distances using much less than quadratic space, such that we can estimate the distance between query vertices in constant time. We will study the inherent trade-off between space of the representation and the stretch (multiplicative approximation disallowing underestimates) of the estimates when the input graph is sparse with m = Õ(n) edges. In this paper, for any fixed positive integers k and ℓ, we obtain stretches = 2k + 1 ± 2/ℓ = 2k + 1 - 2/ℓ, 2k + 1 + 2/ℓ, using space S(α, m) = Õ(m1+2/(α+1)). The query time is O(k + ℓ) = O(1). For integer stretches, this coincides with the previous bounds (odd stretches with ℓ = 1 and even stretches with ℓ = 2). The infinity of fractional stretches between consecutive integers are all new (even though ℓ is fixed as a constant independent of the input, the number of integers ℓ is still countably infinite). We will argue that the new fractional points are not just arbitrary, but that they, at least for fixed stretches below 3, provide a complete picture of the inherent trade-off between stretch and space in m. Consider any fixed stretch α3/2) to Ω̃(m5/3), thus matching their upper bound for stretch 2. For space in terms of m, this is the first hardness matching the space of a non-trivial/sub-quadratic distance oracle.

We study the problem of determining the girth of an unweighted undirected graph. We obtain several new efficient approximation algorithms for graphs with n nodes and m edges and unknown girth g. We consider additive and multiplicative approximations. Additive Approximations. We present: an Õ(n3/m)-time algorithm which returns a cycle of length at most g + 2 if g is even and g + 3 if g is odd. This complements the seminal work of Itai and Rodeh [SIAM J. Computing'78] who gave an algorithm that in O(n2) time finds a cycle of length g if g is even, and g + 1 if g is odd. an Õ(n3/m)-time algorithm which returns a cycle of length at most g′ + 2, where g′ is the length of the shortest even cycle in G. This result complements the work of Yuster and Zwick [SIAM J. Discrete Math'97] who showed how to compute g′ in O(n2) time. Multiplicative Approximations. We present: an Õ(n5/3)-time algorithm which returns a cycle of length at most 3g/2 + z/2 when g is even and 3g/2 + z/2 + 1 when g is odd, where z = –g mod 4, z ∊ {0, 1, 2, 3}. This gives an Õ(n5/3)-time 2-approximation for the girth, the first subquadratic 2-approximation algorithm, resolving an open question of Lingas and Lundell [IPL'09]. an O(n1.968)-time (8/5)-approximation algorithm for the girth in graphs with girth at least 4 (i.e., triangle-free graphs). This is the first subquadratic time (2–ε)-approximation algorithm for the girth for triangle-free graphs, for any ε > 0. We prove that a deterministic algorithm of this kind is not possible for directed graphs, thus showing a strong separation between undirected and directed graphs for girth approximation.

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard. SINR diagrams appear to be fundamental to understanding the behavior of wireless networks, and may play a key role in the development of suitable algorithms for such networks, analogous perhaps to the role played by Voronoi diagrams in the study of proximity queries and related issues in computational geometry. So far, however, the properties of SINR diagrams have not been studied systematically, and most algorithmic studies in wireless networking rely on simplified graph-based models such as the unit disk graph (UDG) model, which conveniently abstract away interference-related complications, and make it easier to handle algorithmic issues, but consequently fail to capture accurately some important aspects of wireless networks. This article focuses on obtaining some basic understanding of SINR diagrams, their properties and their usability in algorithmic applications. Specifically, we have shown that assuming uniform power transmissions, the reception zones are convex and relatively well-rounded. These results are then used to develop an efficient approximation algorithm for a fundamental point location problem in wireless networks.

We obtain three new dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: (i) For any fixed $\varepsilon>0$, a decremental algorithm with an expected total running time of $\tilde{O}(mn)$, where $m$ is the number of edges and $n$ is the number of vertices in the initial graph. Each distance query is answered in $O(1)$ worst-case time, and the stretch of the returned distances is at most $1+\varepsilon$. The algorithm uses $\tilde{O}(n^2)$ space. (ii) For any fixed integer $k\geq1$, a decremental algorithm with an expected total running time of $\tilde{O}(mn)$. Each query is answered in $O(1)$ worst-case time, and the stretch of the returned distances is at most $2k-1$. This algorithm, however, uses only $O(m+n^{1+1/k})$ space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm. (iii) For any fixed $\varepsilon,\delta>0$ and every $t\leq m^{1/2-\delta}$, a fully dynamic algorithm with an expected amortized update time of $\tilde{O}(mn/t)$ and worst-case query time of $O(t)$. The stretch of the returned distances is at most $1+\varepsilon$. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is $b$, then all bounds on the running times are multiplied by $b$.

Let G = ( V,E ) be a directed graph and let P be a shortest path from s to t in G . In the replacement paths problem, we are required to find, for every edge e on P , a shortest path from s to t in G that avoids e . The only known algorithm for solving the problem, even for unweighted directed graphs, is the trivial algorithm in which each edge on the path, in its turn, is excluded from the graph and a shortest paths tree is computed from s . The running time is O ( mn + n 2 log n ). The replacement paths problem is strongly motivated by two different applications: (1) The fastest algorithm to compute the k simple shortest paths between s and t in directed graphs [Yen 1971; Lawler 1972] computes the replacement paths between s and t . Its running time is Õ ( mnk ). (2) The replacement paths problem is used to compute the Vickrey pricing of edges in a distributed network. It was raised as an open problem by Nisan and Ronen [2001] whether it is possible to compute the Vickrey pricing faster than n computations of a shortest paths tree. In this article we present the first nontrivial algorithm for computing replacement paths in unweighted directed graphs (and in graphs with small integer weights). Our algorithm is Monte-Carlo and its running time is Õ ( m √ n ). This result immediately improves the running time of the two applications mentioned above in a factor of √ n . We also show how to reduce the problem of computing k simple shortest paths between s and t to O ( k ) computations of a second simple shortest path from s to t each time in a different subgraph of G . The importance of this result is that computing a second simple shortest path may turn out to be an easier problem than computing the replacement paths, thus, we can focus our efforts to improve the k simple shortest paths algorithm in obtaining a faster algorithm for the second shortest path problem.

We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirected n-node graph with edge weights in {1,..., M} or in a directed n-node graph with edge weights in {-M,..., M} and no negative cycles can be efficiently reduced to finding a minimum weight triangle in an Θ(n)- node undirected graph with weights in {1,..., O(M)}. Roughly speaking, our reductions imply the following surprising phenomenon: a minimum cycle with an arbitrary number of weighted edges can be "encoded" using only three edges within roughly the same weight interval! This resolves a longstanding open problem posed in a seminal work by Itai and Rodeh [SIAM J. Computing 1978] on minimum cycle in unweighted graphs. A direct consequence of our efficient reductions are Õ(Mnω) ≤ 6(Mn2.376)-time algorithms using fast matrix multiplication (FMM) for finding a minimum weight cycle in both undirected graphs with integral weights from the interval [1, M] and directed graphs with integral weights from the interval [-M,M]. The latter seems to reveal a strong separation between the all pairs shortest paths (APSP) problem and the minimum weight cycle problem in directed graphs as the fastest known APSP algorithm has a running time of O(M0.681n2.575) by Zwick [J. ACM 2002]. In contrast, when only combinatorial algorithms are allowed (that is, without FMM) the only known solution to minimum weight cycle is by computing APSP. Interestingly, any separation between the two problems in this case would be an amazing breakthrough as by a recent paper by Vassilevska W. and Williams [FOCS'10], any O(n3-ε)-time algorithm (ε >; 0) for minimum weight cycle immediately implies a O(n3-δ)-time algorithm (δ >; 0) for APSP.

We present an approximate distance oracle for a point set S with n points and doubling dimension Λ. For every ε > 0, the oracle supports (1 + ε)-approximate distance queries in (universal) constant time, occupies space [ε−O(Λ) + 2O(Λ log Λ)]n, and can be constructed in [2O(Λ) log3 n + ε−O(Λ) + 2O(Λ log Λ)]n expected time. This improves upon the best previously known constructions, presented by Har-Peled and Mendel [13]. Furthermore, the oracle can be made fully dynamic with expected O(1) query time and only 2O(Λ) log n + ε−O(Λ) + 2O(Λ log Λ) update time. This is the first fully dynamic (1 + ε)-distance oracle.

We present the first dynamic shortest paths algorithms that make any progress beyond a longstanding O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas). Given a source s, we present an algorithm that maintains (1 + ∊)-approximate shortest paths from s with an expected total update time of over all deletions (so the amortized time is about . The worst-case query time is constant. The best previous result goes back three decades to Even and Shiloach [16] and Dinitz [12]. They show how to decrementally maintain an exact shortest path tree with a total update time of O(mn) (amortized update time O(n)). Roditty and Zwick [22] have shown that O(mn) is actually optimal for exact paths (barring a better combinatorial algorithm for boolean matrix multiplication), unless we are willing to settle for a Ω(n) query time. In fact, until now, even approximate dynamic algorithms were not able to go beyond O(mn). For any fixed integer k ≥ 2, we present an algorithm that decrementally maintains a distance oracle (for all pairs shortest distances) with a total expected update time of (amortized update time about . The space requirement is only O(m + n1+1/k), the stretch of the returned distances is at most 2k − 1 + ∊, and the worst-case query time is O(1). The best previous result of Roditty and Zwick [21] had a total update time of and a stretch of 2k − 1. Note that our algorithm implicitly solves the decremental all-pairs shortest path problem with the same bounds; the best previous approximation algorithm of Roditty and Zwick [21] returned (1 + ∊) approximate distances, but used O(n2) space, and required total update time. As with the previous problem, our algorithm is the first to make progress beyond the O(mn) total update time barrier while maintaining a small query time. We present a general framework for accelerating decremental algorithms. In particular, our main idea is to run existing decremental algorithms on a sparse subgraph (such as a spanner or emulator) of the graph rather than on the original graph G. Although this is a common approach for static approximate shortest-path problems, it has never been used in a decremental setting because maintaining the subgraph H as edges are being deleted from G might require inserting edges into H, thus ruining the “decrementality” of the setting. We overcome this by presenting an emulator whose maintenance only requires a limited number of well-behaved insertions. In other words, we present a general technique for running decremental algorithms on a sparse subgraph of the graph. Once our framework is in place, applying it to any particular decremental algorithm only requires trivial modifications; most of the work consists of showing that these algorithms as they are still work in our restricted fully dynamic setting, where we encounter not just arbitrary deletions (as in the original setting), but also restricted insertions.

This paper considers the problem of computing a minimum weight cycle in weighted undirected graphs. Given a weighted undirected graph G(V, E, w), let C be a minimum weight cycle of G, let w(C) be the weight of C and let wmax (C) be the weight of the maximal edge of C. We obtain three new approximation algorithms for the minimum weight cycle problem: 1. For integral weights from the range [1, M] an algorithm that reports a cycle of weight at most in O(n2 log n(log n + log M)) time. 2. For integral weights from the range [1, M] an algorithm that reports a cycle of weight at most w(C) + wmax (C) in O(n2 log n(log n + log M)) time. 3. For non-negative real edge weights an algorithm that for any ε > 0 reports a cycle of weight at most in time. In a recent breakthrough Vassilevska Williams and Williams [WW10] showed that a subcubic algorithm that computes the exact minimum weight cycle in undirected graphs with integral weights from the range [1, M] implies a subcubic algorithm for computing all-pairs shortest paths in directed graphs with integral weights from the range [–M, M]. This implies that in order to get a subcubic algorithm for computing a minimum weight cycle we have to relax the problem and to consider an approximated solution. Lingas and Lundell [LL09] were the first to consider approximation in the context of minimum weight cycle in weighted graphs. They presented a 2-approximation algorithm for integral weights with O(n2 log n(log n + log M)) running time. They also posed as an open problem the question whether it is possible to obtain a subcubic algorithm with a c-approximation, where c < 2. The current paper answers this question in the affirmative, by presenting an algorithm with 4/3-approximation and the same running time. Surprisingly, the approximation factor of 4/3 is not accidental. We show using the new result of Vassilevska Williams and Williams [WW10] that a subcubic combinatorial algorithm with (4/3 − ε)-approximation, where 0 < ε ≤ 1/3, implies a subcubic combinatorial algorithm for multiplying two boolean matrices.

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental, problems. Subgraph connectivity asks us to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by on vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in $\widetilde{O}(m^{2/3})$ amortized time, where m denotes the number of edges in the graph. This greatly improves upon the previous result [T. M. Chan, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 7–13], which required fast matrix multiplication and had an update time of $O(m^{0.94})$. The new data structure is also simpler. Geometric connectivity asks us to maintain a dynamic set of n geometric objects and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, $\widetilde{O}(n^{2/3})$, for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear time range queries. In particular, we obtain the first sublinear update time for arbitrary two-dimensional line segments: $O^*(n^{9/10})$; for d-dimensional simplices: $O^*(n^{1-\frac{1}{d(2d+1)}})$; and for d-dimensional balls: $O^*(n^{1-\frac{1}{(d+1)(2d+3)}})$.

We show that, for every 0 ≤ p ≤ 1, there is an O ( n 2.575− p /(7.4−2.3 p ) )-time algorithm that given a directed graph with small positive integer weights, estimates the length of the shortest path between every pair of vertices u , v in the graph to within an additive error δ p ( u , v ), where δ( u , v ) is the exact length of the shortest path between u and v . This algorithm runs faster than the fastest algorithm for computing exact shortest paths for any 0 < p ≤ 1. Previously the only way to “beat” the running time of the exact shortest path algorithms was by applying an algorithm of Zwick [2002] that approximates the shortest path distances within a multiplicative error of (1 + ϵ). Our algorithm thus gives a smooth qualitative and quantitative transition between the fastest exact shortest paths algorithm, and the fastest approximation algorithm with a linear additive error. In fact, the main ingredient we need in order to obtain the above result, which is also interesting in its own right, is an algorithm for computing (1 + ϵ) multiplicative approximations for the shortest paths, whose running time is faster than the running time of Zwick's approximation algorithm when ϵ ≪ 1 and the graph has small integer weights.

We give the first improvement to the space/approximation trade-off of distance oracles since the seminal result of Thorup and Zwick [STOC'01]. For unweighted graphs, our distance oracle has size O(n5/3) = O(n1.66⋯) and, when queried about vertices at distance d, returns a path of length 2d + 1. For weighted graphs with m = n2/α edges, our distance oracle has size O(n2/3√α) and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space Ω̃(n2/√α). For unweighted graphs, this implies a Ω̃(n1.5) space lower bound to achieve approximation 2d + 1.

Let $(V,\delta)$ be a finite metric space, where $V$ is a set of $n$ points and $\delta$ is a distance function defined for these points. Assume that $(V,\delta)$ has a constant doubling dimension $d$ and assume that each point $p\in V$ has a disk of radius $r(p)$ around it. The disk graph that corresponds to $V$ and $r(\cdot)$ is a \emph{directed} graph $I(V,E,r)$, whose vertices are the points of $V$ and whose edge set includes a directed edge from $p$ to $q$ if $\delta(p,q)\leq r(p)$. In~\cite{PeRo08} we presented an algorithm for constructing a $(1+\eps)$-spanner of size $O(n/\eps^d \log M)$, where $M$ is the maximal radius $r(p)$. The current paper presents two results. The first shows that the spanner of~\cite{PeRo08} is essentially optimal, i.e., for metrics of constant doubling dimension it is not possible to guarantee a spanner whose size is independent of $M$. The second result shows that by slightly relaxing the requirements and allowing a small perturbation of the radius assignment, considerably better spanners can be constructed. In particular, we show that if it is allowed to use edges of the disk graph $I(V,E,r_{1+\eps})$, where $r_{1+\eps}(p) = (1+\eps)\cdot r(p)$ for every $p\in V$, then it is possible to get a $(1+\eps)$-spanner of size $O(n/\eps^d)$ for $I(V,E,r)$. Our algorithm is simple and can be implemented efficiently.

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.

We present the first approximation algorithm for finding the k shortest simple paths connecting a pair of vertices in a weighted directed graph that breaks the barrier of $mn$. It is deterministic and has a running time of $O(k(m\sqrt{n}+n^{3/2}\log n))$, where m is the number of edges in the graph and n is the number of vertices. Let $s,t\in V$; the length of the ith simple path from s to t computed by our algorithm is at most $\frac{3}{2}$ times the length of the ith shortest simple path from s to t. The best algorithms for computing the exact k shortest simple paths connecting a pair of vertices in a weighted directed graph are due to Yen [Management Sci., 17 (1970/1971), pp. 712–716] and Lawler [Management Sci., 18 (1971/1972), pp. 401–405]. The running time of their algorithms, using modern data structures, is $O(k(mn+n^2\log n))$. Both algorithms are from the early 70s. Although this problem and other variants of the k shortest path problem has drawn a lot of attention during the last three and a half decades, the $O(k(mn+n^2\log n))$ bound is still unbeaten.

Let ( G = ( V(G) , E(G) )) be a directed graph with nonnegative edge lengths and let P be a shortest path from s to t in G . In the replacement paths problem we are required to compute for every edge e in P , the length of a shortest path from s to t that avoids e . The fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in P is removed from the graph in its turn and the distance from s to t in the modified graph is computed. The running time of this algorithm is O ( m n + n 2 log n ), where n = | V(G) | and m = | E(G) |. The replacement paths problem is strongly motivated by two different applications. First, the fastest algorithm to compute the k simple shortest paths from s to t in directed graphs [Yen 1971; Lawler 1972] repeatedly computes the replacement paths from s to t . Its running time is O ( kn ( m + n log n )). Second, the computation of Vickrey pricing of edges in distributed networks can be reduced to the replacement paths problem. An open question raised by Nisan and Ronen [2001] asks whether it is possible to compute the Vickrey pricing faster than the trivial algorithm described in the previous paragraph. In this article we present a near-linear time algorithm for computing replacement paths in weighted planar directed graphs. In particular, the algorithm computes the lengths of the replacement paths in O ( n log 3 n ) time (recall that in planar graphs m = O ( n )). This result immediately improves the running time of the two applications mentioned before by almost a linear factor. Our algorithm is obtained by combining several new ideas with a data structure of Klein [2005] that supports multisource shortest paths queries in planar directed graphs in logarithmic time. Our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). In that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time Õ ( h ), where h is the number of hops in the replacement path. In addition, we can handle the variant in which vertices should be avoided instead of edges.

This article presents an algorithm for constructing a spanner for ad hoc networks whose nodes have variable transmission range. Almost all previous spanner constructions for ad hoc networks assumed that all nodes in the network have the same transmission range. This allowed a succinct representation of the network as a unit disk graph, serving as the basis for the construction. In contrast, when nodes have variable transmission range, the ad hoc network must be modeled by a general disk graph. Whereas unit disk graphs are undirected, general disk graphs are directed. This complicates the construction of a spanner for the network, since currently there are no efficient constructions of low-stretch spanners for general directed graphs. Nevertheless, in this article it is shown that the class of disk graphs enjoys (efficiently constructible) spanners of quality similar to that of unit disk graph spanners. Moreover, it is shown that the new construction can be performed in a localized fashion. Our results use only simple packing arguments, hence all algorithms work for every metric space of constant doubling dimension.

The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection of simultaneously transmitting stations in the plane, it is possible to identify a reception zone for each station, consisting of the points where its transmission is received correctly. The resulting SINR diagram partitions the plane into a reception zone per station and the remaining plane where no station can be heard.

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.

Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental problems:Subgraph connectivity asks to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.)We describe a data structure supporting vertex updates in O~(m^{2/3}) amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC'02], which required fast matrix multiplication and had an update time of O(m^{0.94}). The new data structure is also simpler.Geometric connectivity asks to maintain a dynamic set of ngeometric objects, and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.)Previously, nontrivial fully dynamic results were known onlyfor special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, O~(n^{2/3}), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear-time range queries. In particular, we obtain the first sublinear update time for arbitrary 2D line segments: O*(n^{9/10}); for d-dimensional simplices: O*(n^{1-1/d(2d+1)}); and for d-dimensional balls: O*(n^{1-1/(d+1)(2d+3)}).

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) A decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in $O(mn)$ total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs. (ii) Two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of $O(m\sqrt{n})$, and worst-case query time of $O(\sqrt{n})$. The second is randomized and has an amortized insert/delete time of $O(m^{0.58}n)$ and worst-case query time of $O(m^{0.43})$. This significantly improves the query times of algorithms with similar update times. (iii) A fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of $O(m)$, constant amortized delete time of $O(1)$, and a worst-case query time of $O(n/\log n)$. Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach [J. ACM, 28 (1981), pp. 1–4], Italiano [Inform. Process. Lett., 28 (1988), pp. 5–11], Henzinger and King [Proceedings of the $36$th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, 1995, pp. 664–672], and Frigioni et al. [ACM J. Exp. Algorithmics, 6 (2001), (electronic)].

We obtain a new fully dynamic algorithm for maintaining the transitive closure of a directed graph. Our algorithm maintains the transitive closure matrix in a total running time of O ( mn + ( ins + del ) · n 2 ), where ins ( del ) is the number of insert (delete) operations performed. Here n is the number of vertices in the graph and m is the initial number of edges in the graph. Obviously, reachability queries can be answered in constant time. The algorithm uses only O ( n 2 ) time which is essentially optimal for maintaining the transitive closure matrix. Our algorithm can also support path queries. If v is reachable from u , the algorithm can produce a path from u to v in time proportional to the length of the path. The best previously known algorithm for the problem is due to Demetrescu and Italiano [2000]. Their algorithm has a total running time of O ( n 3 + ( ins + del ) · n 2 ). The query time is also constant. In addition, we also present a simple algorithm for directed acyclic graphs (DAGs) with a total running time of O ( mn + ins · n 2 + del ). Our algorithms are obtained by combining some new ideas with techniques of Italiano [1986, 1988], King [1999], King and Thorup [2001] and Frigioni et al. [2001]. We also note that our algorithms are extremely simple and can be easily implemented.

We introduce the notion of roundtrip-spanners of weighted directed graphs and describe efficient algorithms for their construction. We show that for every integer k ≥ 1 and any ϵ > 0, any directed graph on n vertices with edge weights in the range [1, W ] has a (2 k + ϵ)-roundtrip-spanner with O (min{( k 2 /ϵ) n 1 + 1/ k (log( nW ), ( k /ϵ) 2 n 1 + 1/ k ,(log n ) 2−1/ k }) edges. We then extend these constructions and obtain compact roundtrip routing schemes. For every integer k ≥ 1 and every ϵ > 0, we describe a roundtrip routing scheme that has stretch 4 k + ϵ, and uses at each vertex a routing table of size Õ (( k 2 /ϵ) n 1/ k log( nW )). We also show that any weighted directed graph with arbitrary/ positive edge weights has a 3-roundtrip-spanner with O ( n 3/2 ) edges. This result is optimal. Finally, we present a stretch 3 roundtrip routing scheme that uses local routing tables of size Õ ( n 1/2 ). This routing scheme is essentially optimal. The roundtrip-spanner constructions and the roundtrip routing schemes for directed graphs that we describe are only slightly worse than the best available spanners and routing schemes for undirected graphs. Our roundtrip routing schemes substantially improve previous results of Cowen and Wagner. Our results are obtained by combining ideas of Cohen, Cowen and Wagner, Thorup and Zwick, with some new ideas.

Article Share on Fully dynamic geometric spanners Author: Liam Roditty Weizmann Institute of Science, Rehovot, Israel Weizmann Institute of Science, Rehovot, IsraelView Profile Authors Info & Claims SCG '07: Proceedings of the twenty-third annual symposium on Computational geometryJune 2007 Pages 373–380https://doi.org/10.1145/1247069.1247134Online:06 June 2007Publication History 16citation279DownloadsMetricsTotal Citations16Total Downloads279Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We obtain three dynamic algorithms for the approximate all-pairs shortest paths problem in unweighted undirected graphs: 1) For any fixed /spl epsiv/ > 0, a decremental algorithm with an expected total running time of O(mn), where m is the number of edges and n is the number of vertices in the initial graph. Each distance query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 1 + /spl epsiv/. The algorithm uses O(n/sup 2/) space; 2) For any fixed integer k /spl ges/ 1, a decremental algorithm with an expected total running time of O(mn). Each query is answered in O(1) worst-case time, and the stretch of the returned distances is at most 2k - 1. This algorithm uses, however, only O(m + n/sup 1+1/k/) space. It is obtained by dynamizing techniques of Thorup and Zwick. In addition to being more space efficient, this algorithm is also one of the building blocks used to obtain the first algorithm; 3) For any fixed /spl epsiv/, /spl delta/ > 0 and every t /spl les/ m/sup 1/2-/spl delta//, a fully dynamic algorithm with an expected amortized update time of O(mn/t) and worst-case query time of O(t). The stretch of the returned distances is at most 1+/spl epsiv/. All algorithms can also be made to work on undirected graphs with small integer edge weights. If the largest edge weight is b, then all bounds on the running times are multiplied by b.

We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m+n log n) and a worst-case query time of O(n), where m is the current number of edges in the graph, and n is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. This is the first algorithm that breaks the O(n2) update barrier for all graphs with o(n2) edges.One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting persistency property. Each insert operation creates a new version of the graph. A delete operation deletes edges from emphall versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in O(mα(m,n)) amortized time, and each query in O(1) time, where α(m,n) is a functional inverse of Ackermann's function appearing in the analysis of the union-find data structure. Note that the update time of O(mα(m,n)), in case of a delete operation, is the time needed for updating all versions of the graph.

We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph, and several other algorithms for answering reachability queries without explicitly maintaining a transitive closure matrix. Among our algorithms are: (i) a decremental algorithm for maintaining the transitive closure of a directed graph, through an arbitrary sequence of edge deletions, in O(mn) total expected time, essentially the time needed for computing the transitive closure of the initial graph. Such a result was previously known only for acyclic graphs; (ii) two fully dynamic algorithms for answering reachability queries. The first is deterministic and has an amortized insert/delete time of O(m/spl radic/n), and worst-case query time of O(/spl radic/n). The second is randomized and has an amortized insert/delete time of O(m/sup 0.58/n) and worst-case query time of O(m/sup 0.43/). This significantly improves the query times of algorithms with similar update times; and (iii) a fully dynamic algorithm for maintaining the transitive closure of an acyclic graph. The algorithm is deterministic and has a worst-case insert time of O(m), constant amortized delete time of O(1), and a worst-case query time of O(n/ log n). Our algorithms are obtained by combining several new ideas, one of which is a simple sampling idea used for detecting decompositions of strongly connected components, with techniques of Even and Shiloach (1981), Italiano (1988), Henzinger and King (1995), and Frigioni et al. (2001). We also adapt results of Cohen (1997) on estimating the size of the transitive closure to the dynamic setting.