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+epsilon)$-approximation to Diameter in directed or undirected graphs can be maintained decrementally in total time $m^{1+o(1)}sqrt{n}/epsilon^2$. This nearly matches the static $3/2$-approximation algorithm for the problem that is known to be conditionally optimal.
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. 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. showed that unless the Strong Exponential Time Hypothesis (SETH) fails, no $O(n^{2-epsilon})$ 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-epsilon})$ time algorithm can achieve an approximation factor better than $5/3$. Another fundamental set of graph parameters are the Eccentricities. The Eccentricity of a vertex $v$ is the distance between $v$ and the farthest vertex from $v$. Chechik et al. 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 et al. showed that no $O(n^{2-epsilon})$ 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 under SETH. We also show that no near-linear time algorithm can achieve a better than $2$ approximation for the Eccentricities and that this is essentially tight: we give 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 et al.
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 gra
phs require $Omega(min{n^{omega}, mn})$ time (for $2leqomega<2.373$). In this paper, we drastically improve these runtimes as follows: * Multiplicative Approximations in Nearly Linear Time: We give an algorithm that in $widetilde{O}(m)$ time computes an $widetilde{O}(1)$-multiplicative approximation of the girth as well as an $widetilde{O}(1)$-multiplicative roundtrip spanner with $widetilde{O}(n)$ edges with high probability (w.h.p). * Nearly Tight Additive Approximations: For unweighted graphs and any $alpha in (0,1)$ we give an algorithm that in $widetilde{O}(mn^{1 - alpha})$ time computes an $O(n^alpha)$-additive approximation of the girth w.h.p, and partially derandomize it. We show that the runtime of our algorithm cannot be significantly improved without a breakthrough in combinatorial Boolean matrix multiplication. 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 $Omega(min{n^omega, mn})$ time. Given the traditional difficulty in efficiently processing directed graphs, we hope our techniques may find further applications.
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 $kgeq 1$, there is
an algorithm that computes in $O(2^{k}nlog^2 n)$ time for any set $F$ of size at most $k$ the strongly connected components of the graph $Gsetminus F$. The running time of our algorithm is almost optimal since the time for outputting the SCCs of $Gsetminus 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. These include $L_p$-norms and additively weighted Euclidean distances. Our data structure supports general (con
vex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $O(n log^3 n)$ storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required $O(n^varepsilon)$ time for an update and $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)$ 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.
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 nlog Psi)$ to the query time and $O(n log Psi)$ to the space.
Let $G=(V,E)$ be an undirected graph with $n$ vertices and $m$ edges. We obtain the following new routing schemes: - A routing scheme for unweighted graphs that uses $tilde O(frac{1}{epsilon} n^{2/3})$ space at each vertex and $tilde O(1/epsilon)$-
bit headers, to route a message between any pair of vertices $u,vin V$ on a $(2 + epsilon,1)$-stretch path, i.e., a path of length at most $(2+epsilon)cdot d(u,v)+1$. This should be compared to the $(2,1)$-stretch and $tilde O(n^{5/3})$ space distance oracle of Patrascu and Roditty [FOCS10 and SIAM J. Comput. 2014] and to the $(2,1)$-stretch routing scheme of Abraham and Gavoille [DISC11] that uses $tilde O( n^{3/4})$ space at each vertex. - A routing scheme for weighted graphs with normalized diameter $D$, that uses $tilde O(frac{1}{epsilon} n^{1/3}log D)$ space at each vertex and $tilde O(frac{1}{epsilon}log D)$-bit headers, to route a message between any pair of vertices on a $(5+epsilon)$-stretch path. This should be compared to the $5$-stretch and $tilde O(n^{4/3})$ space distance oracle of Thorup and Zwick [STOC01 and J. ACM. 2005] and to the $7$-stretch routing scheme of Thorup and Zwick [SPAA01] that uses $tilde O( n^{1/3})$ space at each vertex. Since a $5$-stretch routing scheme must use tables of $Omega( n^{1/3})$ space our result is almost tight. - For an integer $ell>1$, a routing scheme for unweighted graphs that uses $tilde O(ellfrac{1}{epsilon} n^{ell/(2ell pm 1)})$ space at each vertex and $tilde O(frac{1}{epsilon})$-bit headers, to route a message between any pair of vertices on a $(3pm2/ell+epsilon,2)$-stretch path. - A routing scheme for weighted graphs, that uses $tilde O(frac{1}{epsilon}n^{1/k}log D)$ space at each vertex and $tilde O(frac{1}{epsilon}log D)$-bit headers, to route a message between any pair of vertices on a $(4k-7+epsilon)$-stretch path.
