We present a randomized algorithm that computes single-source shortest paths (SSSP) in O ( m log 8 ( n ) log W ) time when edge weights are integral and can be negative. 1 This essentially resolves the classic negative-weight SSSP problem. The previous bounds are \(\tilde{O}((m+n^{1.5})\log W)\) [BLNPSSSW FOCS’20] and m 4/3+ o (1) log W [AMV FOCS’20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS’01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic \(\tilde{O}(m\sqrt {n}\log W)\) bound from over three decades ago [Gabow and Tarjan SICOMP’89].

A recent line of work on VC set systems in minor-free (undirected) graphs, starting from Li and Parter [LP19], who constructed a new VC set system for planar graphs, has given surprising algorithmic results [LP19, Le23, DHV20, FHMWN20]. In this work, we initialize a more systematic study of VC set systems for minor-free graphs and their applications in both undirected graphs and directed graphs (a.k.a digraphs). More precisely:

Given a simple n-vertex, m-edge graph G undergoing edge insertions and deletions, we give two new fully dynamic algorithms for exactly maintaining the edge connectivity of G in Õ(n) worst-case update time and Õ(m1-1/16) amortized update time, respectively. Prior to our work, all dynamic edge connectivity algorithms assumed bounded edge connectivity, guaranteed approximate solutions, or were restricted to edge insertions only. Our results answer in the affirmative an open question posed by Thorup [Combinatorica'07].

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q , and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = ~ Θ( n/√ S ) or Q = ~Θ( n 5/2 /S 3/2 ). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n 1+ o (1) and almost optimal query time n o (1) . More precisely, we achieve the following space-time tradeoffs: n 1+ o (1) space and log 2+ o (1) n query time, n log 2+ o (1) n space and n o (1) query time, n 4/3+ o (1) space and log 1+ o (1) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.

We present a randomized algorithm that computes single-source shortest paths (SSSP) in $O\left(m \log ^{8}(n) \log W\right)$ time when edge weights are integral and can be negative.1This essentially resolves the classic negative-weight SSSP problem. The previous bounds are $\tilde{O}\left(\left(m+n^{1.5}\right) \log W\right)$ [BLNPSSSW FOCS’20] and $m^{4 / 3+o(1)} \log W$ [AMV FOCS’20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS’01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic $O(m \sqrt{n} \log W)$ bound from over three decades ago [Gabow and Tarjan SICOMP’89].

In the planar, dynamic All-Pairs Shortest Paths (APSP) problem, a planar, weighted digraph G undergoes a sequence of edge weight updates and the goal is to maintain a data structure on G, that can quickly answer distance queries between any two vertices x,y ∊ V(G). The currently best algorithms [FOCS'01, SODA'05] for this problem require Õ(n2/3) worst-case update and query time, while conditional lower bounds [FOCS'16] show that either update or query time is needed1. In this article, we present the first algorithm with near-optimal worst-case update and query time for the offline setting, where the update sequence is given initially. This result is obtained by giving the first offline dynamic algorithm for maintaining dense distance graphs (DDGs) faster than recomputing from scratch after each update. Further, we also present an online algorithm for the incremental APSP problem with worst-case update/query time. This allows us to reduce the online dynamic APSP problem to the online decremental APSP problem, which constitutes partial progress even for the online version of this notorious problem.

This issue of SICOMP contains six specially selected papers from STOC 2020, the Fifty-second Annual ACM Symposium on the Theory of Computing, which was held June 22--26, 2020, initially planned at Chicago, Illinois, but due to COVID-19 was an online conference in the end. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough reviewing process of SICOMP. The program committee for STOC 2020 consisted of an executive committee made up of Nima Anari, Boaz Barak, Sébastien Bubeck, Mark Bun, Arkadev Chattopadhyay, Chandra Chekuri, Julia Chuzhoy, Marek Cygan, Ilias Diakonikolas, Yevgeniy Dodis, Sebastian Forster, Ankit Garg, Nika Haghtalab, Prahladh Harsha, Justin Holmgren, Piotr Indyk, Rahul Jain, Sanjeev Khanna, Dakshita Khurana, Pravesh Kothari, Robert Krauthgamer, Marvin Künnemann, Tengyu Ma, Rafael Oliveira, Merav Parter, Sofya Raskhodnikova, Robert Robere, Dana Ron, Noga Ron-Zewi, Thatchaphol Saranurak, Balasubramanian Sivan, Christian Sohler, Madhur Tulsiani, Omri Weinstein, Christian Wulff-Nilsen, and Henry Yuen. The program chair was Julia Chuzhoy. Included in this issue are the following papers: ``Explicit Near-Ramanujan Graphs of Every Degree" by Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes shows a deterministic poly$(n)$-time algorithm that outputs a $d$-regular graph on $\Theta(n)$ vertices that is $\epsilon$-near-Ramanujan. ``Reducing Path TSP to TSP" by Vera Traub, Jens Vygen, and Rico Zenklusen presents a black-box reduction from the path version of the traveling salesman problem (Path TSP) to the classical tour version (TSP). ``Nearly Optimal Static Las Vegas Succinct Dictionary" by Huacheng Yu obtains a randomized dictionary data structure using ${OPT}+{poly}\lg n+O(\lg^{(\ell)} U)$ bits of space with expected constant query time for the static dictionary problem. ``Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions" by Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh Raj Saxena, and S. Matthew Weinberg provides the first separation in the approximation guarantee achievable by truthful and nontruthful combinatorial auctions with polynomial communication. ``Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization" by Lijie Chen and Hanlin Ren establish a connection between nondeterministic algorithms estimating the acceptance probability of a given circuit and average-case lower bounds for nondeterministic time classes. ``Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs" by Siddharth Bhandari and Sayantan Chakraborty presents a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k>3\Delta$ and returns a random proper $k$-coloring of $G$. We thank the authors, the STOC 2020 program committee, the STOC 2020 external reviewers, and the SICOMP referees for all of their hard work. Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen - Guest editors

A ($1+\epsilon$) -approximate distance oracle of an edge-weighted graph is a data structure that returns an approximate shortest path distance between any two query vertices up to a ($1+\epsilon$) factor. Thorup (FOCS 2001, JACM 2004) and Klein (SODA 2002) independently constructed a ($1+\epsilon$) -approximate distance oracle with$O(n\log n)$space, measured in number of words, and$O(1)$query time when$G$is an undirected planar graph with$n$vertices and$\epsilon$is a fixed constant. Many follow-up works gave ($1+\epsilon$) -approximate distance oracles with various trade-offs between space and query time. However, improving$O(n\log n)$space bound without sacrificing query time remains an open problem for almost two decades. In this work, we resolve this problem affirmatively by constructing a ($1+\epsilon$) approximate distance oracle with optimal$O(n)$space and$O(1)$query time for undirected planar graphs and fixed$\epsilon$. We also make substantial progress for planar digraphs with non-negative edge weights. For fixed$\epsilon > 0$, we give a ($1+\epsilon$) -approximate distance oracle with space$o(n\log(Nn))$and$O(\log\log(Nn)$query time; here$N$is the ratio between the largest and smallest positive edge weight. This improves Thorup's (FOCS 2001, JACM 2004)$O(n\log(Nn)\log n)$space bound by more than a logarithmic factor while matching the query time of his structure. This is the first improvement for planar digraphs in two decades, both in the weighted and unweighted setting.

Given a directed graph $G = (V,E)$, undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n = |V|$, we consider the problem of maintaining all-pairs shortest paths (APSP) in $G$. Whilst this problem has been studied in a long line of research [ACM'81, FOCS'99, FOCS'01, STOC'02, STOC'03, SWAT'04, STOC'13] and the problem of $(1+ε)$-approximate, weighted APSP was solved to near-optimal update time $\tilde{O}(mn)$ by Bernstein [STOC'13], the problem has mainly been studied in the context of oblivious adversaries, which assumes that the adversary fixes the update sequence before the algorithm is started. In this paper, we make significant progress on the problem in the setting where the adversary is adaptive, i.e. can base the update sequence on the output of the data structure queries. We present three new data structures that fit different settings: We first present a deterministic data structure that maintains exact distances with total update time $\tilde{O}(n^3)$. We also present a deterministic data structure that maintains $(1+ε)$-approximate distance estimates with total update time $\tilde O(\sqrt{m} n^2/ε)$ which for sparse graphs is $\tilde O(n^{2+1/2}/ε)$. Finally, we present a randomized $(1+ε)$-approximate data structure which works against an adaptive adversary; its total update time is $\tilde O(m^{2/3}n^{5/3} + n^{8/3}/(m^{1/3}ε^2))$ which for sparse graphs is $\tilde O(n^{2+1/3})$. Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. [STOC'02] and maintains the distance matrix in near-optimal time. Our approximate data structures improve upon the best data structures against an adaptive adversary which have $\tilde{O}(mn^2)$ total update time [JACM'81, STOC'03].

Given an undirected n-vertex planar graph G = (V,E,ω) with non-negative edge weight function ω:E → ℝ and given an assigned label to each vertex, a vertex-labeled distance oracle is a data structure which for any query consisting of a vertex u and a label λ reports the shortest path distance from u to the nearest vertex with label λ. We show that if there is a distance oracle for undirected n-vertex planar graphs with non-negative edge weights using s(n) space and with query time q(n), then there is a vertex-labeled distance oracle with Õ(s(n)) space and Õ(q(n)) query time. Using the state-of-the-art distance oracle of Long and Pettie [Long and Pettie, 2021], our construction produces a vertex-labeled distance oracle using n^{1+o(1)} space and query time Õ(1) at one extreme, Õ(n) space and n^o(1) query time at the other extreme, as well as such oracles for the full tradeoff between space and query time obtained in their paper. This is the first non-trivial exact vertex-labeled distance oracle for planar graphs and, to our knowledge, for any interesting graph class other than trees.

Given an undirected, unweighted planar graph $G$ with $n$ vertices, we present a truly subquadratic size distance oracle for reporting exact shortest-path distances between any pair of vertices of $G$ in constant time. For any $\varepsilon > 0$, our distance oracle takes up $O(n^{5/3+\varepsilon})$ space and is capable of answering shortest-path distance queries exactly for any pair of vertices of $G$ in worst-case time $O(\log (1/\varepsilon))$. Previously no truly sub-quadratic size distance oracles with constant query time for answering exact all-pairs shortest paths distance queries existed.

In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph G = (V, E, w) undergoing edge deletions and a source vertex r ∈ V; let n=|V|, m=|E| and W be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from r to all vertices in V and can answer distance queries in O(1) time, as well as return the corresponding path P in O(|P|) time. This problem was first considered by Even and Shiloach [JACM'81], who provided an algorithm with total update time O(mn) for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS'95, STOC'99]. There are conditional lower bounds showing that O(mn) is in fact near-optimal [ESA'04, FOCS'14, STOC'15, STOC'20]. In a breakthrough result, Forster et al. showed that total update time min{m7/6n2/3+o(1), m3/4n5/4+o(1)} polylog(W) = mn0.9+o(1)polylog (W), is possible if the algorithm is allowed to return ( 1 +ε)-approximate paths, instead of exact ones [STOC'14, ICALP'15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA'20] provided a new approach for the problem, which yields total time ~O(min{m2/3n4/3logW, (mn)7/8logW}) = ~O(min{n8/3logW, mn3/4logW}). Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental ( 1+ε)-approximate SSSP data structure with total update time ~O(n2log4W/ε). Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time ~O(mn2/3log3W/ε). Combined, these data structures dominate all previous results. Like all previous o(mn) algorithms that can return a path (not just a distance estimate), our result is randomized and assumes an oblivious adversary. Our framework effectively allows us to reduce SSSP in general graphs to the same problem in directed acyclic graphs (DAGs). We believe that our framework has significant potential to influence future work on directed SSSP, both in the dynamic model and in others.

In the decremental (1 + ϵ)-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph G = (V, E) with n = |V|, m = |E|, undergoing edge deletions, and a distinguished source s ϵ V, and we are asked to process edge deletions efficiently and answer queries for distance estimates G(s, v) for each v ϵ V, at any stage, such that G(s, v) ≤ G(s, v) ≤ (1 + ϵ)distG(s, v). In the decremental (1 + ϵ)-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates G(u, v) for every u,v ϵ V. In this article, we consider the problems for undirected, unweighted graphs. We present a new deterministic algorithm for the decremental (1 + ϵ)-approximate SSSP problem that takes total update time O(mn0.5+o(1)). Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time Õ(n2) and the best existing algorithm for sparse graphs with running time [SODA 2017] whenever m = O(n1.5−o(1)). In order to obtain our new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic sparse emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental (1 + ϵ)-approximate APSP problem with near-optimal total running time Õ(mn/ϵ) matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].

Given a dynamic digraph G = (V, E) undergoing edge deletions and given s ϵ V and constant ϵ with 0 < ϵ ≤ 1, we consider the problem of maintaining (1+ϵ)-approximate shortest path distances from s to all vertices in G over the sequence of deletions. Even and Shiloach (J. ACM’81) give a deterministic data structure for the exact version of the problem in unweighted graphs with total update time O(mn). Henzinger et al. (STOC’14, ICALP’15) give a Monte Carlo data structure for the approximate version with an improved total update time bound of O(mn0.9+°(1) log W) with better bounds for sufficiently dense and sufficiently sparse graphs; here W is the ratio between the largest and smallest edge weight. A drawback of their data structure and in fact of all previous randomized data structures is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This severely limits its application as a black box inside algorithms. We present the following (1 + ϵ)-approximate data structures: the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time Õ(m2/3n4/3)1 for unweighted graphs and Õ(m3/4n5/4 log W) for weighted graphs, the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time for unweighted graphs and Õ(m2/3n4/3 log W) for weighted graphs, the third data structure is Monte Carlo and is correct w.h.p. against an oblivious adversary; it has total expected update time Õ((mn)7/8 log W) = Õ(mn3/4 log W). Each of our data structures can report the length of a (1 + ϵ)-approximate shortest path from s to any query vertex in constant time at any point during the sequence of updates; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al. for all graph densities. For instance, when m = Θ(n2), our second result improves their bound from O(n2+3/4+o(1) log W) to Õ(n2+1/2) in the unweighted setting and to Õ(n2+2/3 log W) in the weighted setting. When m = Θ(n), our third result gives an improvement from O(n1+5/6+o(1) log W) to Õ(n1+3/4 log W). Furthermore, our first data structure is the first to improve on the O(mn) bound of Even and Shiloach for all but the sparsest graphs while still working against an adaptive adversary and works even in weighted graphs; this answers an open problem by Henzinger et al.

Given a directed weighted graph G = (V, E) undergoing vertex insertions and deletions, the All-Pairs Shortest Paths (APSP) problem asks to maintain a data structure that processes updates efficiently and returns after each update the distance matrix to the current version of G. In two breakthrough results, Italiano and Demetrescu [STOC'03] presented an algorithm that requires Õ(n2) amortized update time, and Thorup showed in [STOC'05] that worst-case update time Õ(n2+3/4) can be achieved. In this article, we make substantial progress on the problem. We present the following new results: We present the first deterministic data structure that breaks the Õ(n2+3/4) worst-case update time bound by Thorup which has been standing for almost 15 years. We improve the worst-case update time to Õ(n2+5/7) = Õ(n2.71) and to Õ(n2+3/5) = Õ(n2.6) for unweighted graphs. We present a simple deterministic algorithm with Õ(n2+3/4) worst-case update time (Õ(n2+2/3) for unweighted graphs), and a simple Las-Vegas algorithm with worst-case update time Õ(n2+2/3) (Õ(n2+1/2) for unweighted graphs) that works against a non-oblivious adversary. Both data structures require space Õ(n2). These are the first exact dynamic algorithms with trulysubcubic update time and space usage. This makes significant progress on an open question posed in multiple articles [COCOON'01, STOC '03, ICALP '04, Encyclopedia of Algorithms '08] and is critical to algorithms in practice [TALG '06] where large space usage is prohibitive. Moreover, they match the worst-case update time of the best previous algorithms and the second algorithm improves upon a Monte-Carlo algorithm in a weaker adversary model with the same running time [SODA '17].

Graph spanners are well-studied and widely used both in theory and practice. In a recent breakthrough, Chechik and Wulff-Nilsen [Shiri Chechik and Christian Wulff-Nilsen, 2018] improved the state-of-the-art for light spanners by constructing a (2k-1)(1+epsilon)-spanner with O(n^(1+1/k)) edges and O_epsilon(n^(1/k)) lightness. Soon after, Filtser and Solomon [Arnold Filtser and Shay Solomon, 2016] showed that the classic greedy spanner construction achieves the same bounds. The major drawback of the greedy spanner is its running time of O(mn^(1+1/k)) (which is faster than [Shiri Chechik and Christian Wulff-Nilsen, 2018]). This makes the construction impractical even for graphs of moderate size. Much faster spanner constructions do exist but they only achieve lightness Omega_epsilon(kn^(1/k)), even when randomization is used. The contribution of this paper is deterministic spanner constructions that are fast, and achieve similar bounds as the state-of-the-art slower constructions. Our first result is an O_epsilon(n^(2+1/k+epsilon')) time spanner construction which achieves the state-of-the-art bounds. Our second result is an O_epsilon(m + n log n) time construction of a spanner with (2k-1)(1+epsilon) stretch, O(log k * n^(1+1/k) edges and O_epsilon(log k * n^(1/k)) lightness. This is an exponential improvement in the dependence on k compared to the previous result with such running time. Finally, for the important special case where k=log n, for every constant epsilon>0, we provide an O(m+n^(1+epsilon)) time construction that produces an O(log n)-spanner with O(n) edges and O(1) lightness which is asymptotically optimal. This is the first known sub-quadratic construction of such a spanner for any k = omega(1). To achieve our constructions, we show a novel deterministic incremental approximate distance oracle. Our new oracle is crucial in our construction, as known randomized dynamic oracles require the assumption of a non-adaptive adversary. This is a strong assumption, which has seen recent attention in prolific venues. Our new oracle allows the order of the edge insertions to not be fixed in advance, which is critical as our spanner algorithm chooses which edges to insert based on the answers to distance queries. We believe our new oracle is of independent interest.

Lightness and sparsity are two natural parameters for Euclidean $(1+\varepsilon)$-spanners. Classical results show that, when the dimension $d\in \mathbb{N}$ and $\varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits a $(1+\varepsilon)$-spanner with $O(n)$ edges and weight proportional to that of the Euclidean minimum spanning tree of $S$. In a recent breakthrough, Le and Solomon [Proceedings of FOCS, 2019, pp. 1078--1100] established the precise dependencies on $\varepsilon>0$, for constant $d\in \mathbb{N}$, of the minimum lightness and sparsity of $(1+\varepsilon)$-spanners, and observed that Steiner points can substantially improve the lightness and sparsity of a $(1+\varepsilon)$-spanner. They gave upper bounds of $\tilde{O}(\varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $d\geq 3$ and $\tilde{O}(\varepsilon^{-(d-1)/2})$ for the minimum sparsity in $d$-space for all $d\geq 1$. Subsequently, Le and Solomon [LIPIcs Leibniz Int. Proc. Inform. 173, Schloss Dagstuhl, Wadern, 2020, pp. 67:1--67:22] constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\log\Delta)$ in the plane, where $\Delta\in \Omega(\sqrt{n})$ is the spread of $S$, defined as the ratio between the maximum and the minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner $(1+\varepsilon)$-spanners. We establish lower bounds of $\Omega(\varepsilon^{-d/2})$ for the lightness and $\Omega(\varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all constant $d\geq 2$. Our lower bound constructions generalize previous constructions by Le and Solomon, but the analysis substantially simplifies previous work, using new geometric insight, focusing on the directions of edges. Next, we show that for every finite set of points in the plane and every $\varepsilon\in (0,1]$, there exists a Euclidean Steiner $(1+\varepsilon)$-spanner of lightness $O(\varepsilon^{-1})$; this matches the lower bound for $d=2$. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.

Computing the Strongly-Connected Components (SCCs) in a graph G=(V,E) is known to take only O(m+n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = |E|, n=|V|. For fully-dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e. graphs that undergo edge deletions.

Computing the strongly connected Components (SCCs) in a graph $G=(V,E)$ is known to take only $O(m + n)$ time using an algorithm by Tarjan [ SIAM J. Comput., 1 (1972), pp. 146--160] where $m = |E|$, $n=|V|$. For fully dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e., graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time $\tilde{O}(m)$, thus only a polylogarithmic factor from the optimal running time. (We use $\tilde{O}(f(n))$ notation to suppress logarithmic factors, i.e., $g(n) = \tilde{O}(f(n))$ if $g(n) = O(f(n) {polylog}(n)).$) Our result also yields the fastest algorithm for the decremental single-source reachability (SSR) problem which can be reduced to decrementally maintaining SCCs. Using a well-known reduction, we use our decremental result to achieve new update/query-time trade-offs in the fully dynamic setting. We can maintain the reachability of pairs $S \times V$, $S \subseteq V$ in fully dynamic graphs with update time $\tilde{O}(\frac{|S|m}{t})$ and query time $O(t)$ for all $t \in [1,|S|]$; this matches to polylogarithmic factors the best all-pairs reachability algorithm for $S = V$.

We present an O(n1.5)-space distance oracle for directed planar graphs that answers distance queries in O(log n) time. Our oracle both significantly simplifies and significantly improves the recent oracle of Cohen-Addad, Dahlgaard and Wulff-Nilsen [FOCS 2017], which uses O(n5/3)-space and answers queries in O(log n) time. We achieve this by designing an elegant and efficient point location data structure for Voronoi diagrams on planar graphs. We further show a smooth tradeoff between space and query-time. For any S ∊ [n, n2], we show an oracle of size S that answers queries in Õ(max{1, n1.5/S}) time. This new tradeoff is currently the best (up to polylogarithmic factors) for the entire range of S and improves by polynomial factors over all previously known tradeoffs for the range S ∊ [n, n5/3].

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

We answer the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assumed to be points moving with at most unit speed. That the lakes are rectifiable means that their boundaries are finitely long. This requirement is to avoid pathological examples where the man survives forever because any path to the lions is infinitely long. We show that the answer to the question is not always "yes", by giving an example of a region R in the plane where the man has a strategy to survive forever. R is a polygonal region with holes and the exterior and interior boundaries are pairwise disjoint, simple polygons. Our construction is the first truly two-dimensional example where the man can survive. Next, we consider the following game played on the entire plane instead of a bounded area: There is any finite number of unit speed lions and one fast man who can run with speed 1+epsilon for some value epsilon>0. Can the man always survive? We answer the question in the affirmative for any constant epsilon>0.

We show that every H-minor-free graph has a light (1+≥ilon)-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung \cite{GH12}. Our lightness bound is \[O\left(\frac{\sigma_H}{≥ilon^3}\log \frac{1}{≥ilon}\right)\] where \sigma_H = |V(H)|√{\log |V(H)|} is the sparsity coefficient of H-minor-free graphs. That is, it has a practical dependency on the size of the minor H. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in H-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is 2^{O_H\left(\frac{1}{≥ilon^4}\log \frac{1}{≥ilon}\right)}n^{O(1)} where O_H ignores dependencies on the size of H. Our techniques significantly deviate from existing lines of research on spanners for H-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs[6].

For a given a graph, a distance oracle is a data structure that answers distance queries between pairs of vertices. We introduce an O(n5/3)-space distance oracle which answers exact distance queries in O(log n) time for n-vertex planar edge-weighted digraphs. All previous distance oracles for planar graphs with truly subquadratic space (i.e., space O(n2-ϵ)for some constant ϵ > 0) either required query time polynomial in n or could only answer approximate distance queries. Furthermore, we show how to trade-off time and space: for any S ≥ n3/2, we show how to obtain an S-space distance oracle that answers queries in time O( n5/2/S3/2logn). This is a polynomial improvement over the previous planar distance oracles with o(n1/4) query time.

We present a Las Vegas algorithm for dynamically maintaining a minimum spanning forest of an nnode graph undergoing edge insertions and deletions. Our algorithm guarantees an O(no(1)) worst-case update time with high probability. This significantly improves the two recent Las Vegas algorithms by Wulff-Nilsen [2] with update time O(n0.5-ε) for some constant ε > 0 and, independently, by Nanongkai and Saranurak [3] with update time O(n0.494) (the latter works only for maintaining a spanning forest). Our result is obtained by identifying the common framework that both two previous algorithms rely on, and then improve and combine the ideas from both works. There are two main algorithmic components of the framework that are newly improved and critical for obtaining our result. First, we improve the update time from O(n0.5-ε) in [2] to O(no(1)) for decrementally removing all low-conductance cuts in an expander undergoing edge deletions. Second, by revisiting the “contraction technique” by Henzinger and King [4] and Holm et al. [5], we show a new approach for maintaining a minimum spanning forest in connected graphs with very few (at most (1 + o(1))n) edges. This significantly improves the previous approach in [2], [3] which is based on Frederickson's 2-dimensional topology tree [6] and illustrates a new application to this old technique.

We give a Las Vegas data structure which maintains a minimum spanning forest in an n-vertex edge-weighted undirected dynamic graph undergoing updates consisting of any mixture of edge insertions and deletions. Each update is supported in O(n1/2 - c) worst-case time w.h.p. where c > 0 is some constant, and this bound also holds in expectation. This is the first data structure achieving an improvement over the O(√n) deterministic worst-case update time of Eppstein et al., a bound that has been standing for 25 years. In fact, it was previously not even known how to maintain a spanning forest of an unweighted graph in worst-case time polynomially faster than Θ(√n). Our result is achieved by first giving a reduction from fully-dynamic to decremental minimum spanning forest preserving worst-case update time up to logarithmic factors. Then decremental minimum spanning forest is solved using several novel techniques, one of which involves keeping track of low-conductance cuts in a dynamic graph. An immediate corollary of our result is the first Las Vegas data structure for fully-dynamic connectivity where each update is handled in worst-case time polynomially faster than Θ(√n) w.h.p.; this data structure has O(1) worst-case query time.

We give an $O(n \log^3 n)$ algorithm that, given an $n$-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a minimum $st$-cut in $G$? We solve this problem in preprocessing time $O(n\log^3 n)$ for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space $O(n)$ that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is $2^{O(g^2)}$.

An adjacency labeling scheme labels the n nodes of a graph with bit strings in a way that allows, given the labels of two nodes, to determine adjacency based only on those bit strings.Though many graph families have been meticulously studied for this problem, a non-trivial labeling scheme for the important family of power-law graphs has yet to be obtained.This family is particularly useful for social and web networks as their underlying graphs are typically modelled as power-law graphs.Using simple strategies and a careful selection of a parameter, we show upper bounds for such labeling schemes of Õ( α √ n) for power law graphs with coefficient α, as well as nearly matching lower bounds.We also show two relaxations that allow for a label of logarithmic size, and extend the upper-bound technique to produce an improved distance labeling scheme for power-law graphs.

A labeling scheme is a method of distributing the information about the structure of a graph among its vertices by assigning short labels, such that a selected function on pairs of vertices can be computed using only their labels. A labeling scheme consists of an encoder that has access to the entire graph and assigns labels to vertices, and a decoder that has access to only the labels of a smaller set of vertices (typically a pair) and returns information about this subset (e.g., whether two vertices are adjacent, or the distance between them in the graph). The main objective is to minimize the maximum label size: the maximum number of bits used in a label of any vertex. Among the applications of labeling schemes are XML search engines, mapping services, and internet routing.

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

We consider approximate distance oracles for edge-weighted n-vertex undirected planar graphs. Given fixed ∊ > 0, we present a (1 + ∊)-approximate distance oracle with O(n(log log n)2) space and O((log log n)3) query time. This improves the previous best product of query time and space of the oracles of Thorup (FOCS 2001, J. ACM 2004) and Klein (SODA 2002) from O(n log n) to O(n(log log n)5).

For an undirected n -vertex planar graph G with nonnegative edge weights, we consider the following type of query: given two vertices s and t in G , what is the weight of a min st -cut in G ? We show how to answer such queries in constant time with O ( n log 4 n ) preprocessing time and O ( n log n ) space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min cut and the minimum-cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum-cycle basis in O ( n log 4 n ) time and O ( n log n ) space. Additionally, an explicit representation can be obtained in O ( C ) time and space where C is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead or deterministically with an additional log 2 n factor in the preprocessing times.

Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 2, we show that a (2k − 1)-approximate distance oracle for G of size O(kn1+1/k) and with O(log k) query time can be constructed in O(min{kmn1/k, √km + kn1+c/ √k}) time for some constant c. This improves the O(k) query time of Thorup and Zwick. Furthermore, for any 0 < ∊ ≤ 1, we give an oracle of size O(kn1+1/k) that answers ((2 + ∊)k)-approximate distance queries in O(1/∊) time. At the cost of a k-factor in size, this improves the 128k approximation achieved by the constant query time oracle of Mendel and Naor and approaches the best possible tradeoff between size and stretch, implied by a widely believed girth conjecture of Erdős. We can match the O(n1+1/k) size bound of Mendel and Naor for any constant ∊ > 0 and k = O (log n/ log log n).

We give new deterministic bounds for fully-dynamic graph connectivity. Our data structure supports updates (edge insertions/deletions) in O(log2 n/ log log n) amortized time and connectivity queries in O(log n/ log log n) worst-case time, where n is the number of vertices of the graph. This improves the deterministic data structures of Holm, de Lichtenberg, and Thorup (STOC 1998, J. ACM 2001) and Thorup (STOC 2000) which both have O(log2 n) amortized update time and O(log n/log log n) worst-case query time. Our model of computation is the same as that of Thorup, i.e., a pointer machine with standard AC0 instructions.

Let $G = (V, E)$ be a planar $n$-vertex digraph. Consider the problem of computing max $st$-flow values in $G$ from a fixed source $s$ to all sinks $t \in V \set minus \{s\}$. We show how to solve this problem in near-linear $O(n \log^3 n)$ time. Previously, nothing better was known than running a single-source single-sink max flow algorithm $n-1$ times, giving a total time bound of $O(n^2 \log n)$ with the algorithm of Borradaile and Klein. An important implication is that all-pairs max $st$-flow values in $G$ can be computed in near-quadratic time. This is close to optimal as the output size is $\Theta(n^2)$. We give a quadratic lower bound on the number of distinct max flow values and an $\Omega(n^3)$ lower bound for the total size of all min cut-sets. This distinguishes the problem from the undirected case where the number of distinct max flow values is $O(n)$. Previous to our result, no algorithm which could solve the all-pairs max flow values problem faster than the time of $\Theta(n^2)$ max-flow computations for every planar digraph was known. This result is accompanied with a data structure that reports min cut-sets. For fixed $s$ and all $t$, after $O(n^{1.5} \log^2 n)$ preprocessing time, it can report the set of arcs $C$ crossing a min $st$-cut in $O(|C|)$ time.

Given an undirected graph G with m edges, n vertices, and non-negative edge weights, and given an integer k ≥ 1, we show that for some universal constant c, a (2k − 1)-approximate distance oracle for G of size O(kn1+1/k) can be constructed in time and can answer queries in O(k) time. We also give an oracle which is faster for smaller k. Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all k ≥ 6 and improve the O(kmn1/k) time bound of Thorup and Zwick except for very sparse graphs and small k. When m = Ω(n1+c/√k) and k = O(1), our oracle is optimal w.r.t. both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erdős.

We give an O(n log3n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

Alon, Seymour, and Thomas generalized Lipton and Tarjan's planar separator theorem and showed that a Kh- minor free graph with n vertices has a separator of size at most h3/2√n. They gave an algorithm that, given a graph G with m edges and n vertices and given an integer h ≥ 1, outputs in O(√hnm) time such a separator or a Ku-minor of G. Plotkin, Rao, and Smith gave an O(hm√/n log n) time algorithm to find a separator of size O(h√n log n). Kawarabayashi and Reed improved the bound on the size of the separator to h√n and gave an algorithm that finds such a separator in O(n1+ϵ) time for any constant ϵ >; 0, assuming h is constant. This algorithm has an extremely large dependency on h in the running time (some power tower of h whose height is itself a function of h), making it impractical even for small h. We are interested in a small polynomial time dependency on h and we show how to find an O (h√n log n)-size separator or report that G has a Ku-minor in O(poly(h)n5/4+ϵ) time for any constant ϵ >; 0. We also present the first O(poly(h)n) time algorithm to find a separator of size 0(nc) for a constant ϵ2 + ϵ/ℓ) time algorithm that either produces a Kh-minor of depth O(ℓ log n) or a separator of size at most O(n/ℓ + ℓh2log n). This improves the shallow minor algorithm of Plotkin, Rao, and Smith when m = Ω(n1+ϵ). We get a similar running time improvement for an approximation algorithm for the problem of finding a largest Kh-minor in a given graph.

We study the min st-cut and max st-flow problems in planar graphs, both in static and in dynamic settings. First, we present an algorithm that given an undirected planar graph and two vertices s and t computes a min st-cut in O(n log log n) time. Second, we show how to achieve the same bound for the problem of computing a max st-flow in an undirected planar graph. These are the first algorithms breaking the O(n log n) barrier for those two problems, which has been standing for more than 25 years. Third, we present a fully dynamic algorithm maintaining the value of the min st-cuts and the max st-flows in an undirected plane graph (i.e., a planar graph with a fixed embedding): our algorithm is able to insert and delete edges and answer queries for min st-cut/max st-flow values between any pair of vertices s and t in O(n(2/3) log(8/3) n) time per operation. This result is based on a new dynamic shortest path algorithm for planar graphs which may be of independent interest. We remark that this is the first known non-trivial dynamic algorithm for min st-cut and max st-flow.

For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log5n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min st-cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Our oracle can be extended to report the min st-cuts in time proportional to their size. Since all-pairs min si-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log5n) time and O(n log n) space and an explicit representation with additional O(C) time and space where G is the size of the basis. To obtain our results, we require that shortest paths be unique; this assumption can be removed deterministically with an additional O(log2n) running-time factor.

In a graph G with non-negative edge lengths, let P be a shortest path from a vertex s to a vertex t. We consider the problem of computing, for each edge e on P, the length of a shortest path in G from s to t that avoids e. This is known as the replacement paths problem. We give a linear-space algorithm with O(n log n) running time for n-vertex planar directed graphs. The previous best time bound was O(n log2 n).

Abstract Given a finite set Z of n points, called terminals, in ℝd, the Rectilinear Steiner Tree Problem asks for a tree of minimal L1‐length spanning Z. An optimal solution has a unique decomposition into full Steiner trees (FSTs). By using geometric properties and combinatorial arguments, we bound the expected number of FSTs satisfying simple necessary conditions for being part of an optimal solution. More specifically, we show that the expected number of FSTs spanning exactly K terminals and satisfying the empty lune property, a weak version of the bottleneck property, and the so‐called empty hyperbox property is O(n(log log n)2(d−1)) for K = 3 and O(n(log log n)d−1 log K−2n) for K > 3, assuming terminals are randomly distributed in a hypercube with a uniform distribution. In the plane, we improve an earlier bound by showing that the expected number of FSTs with the Hwang form spanning exactly K terminals and satisfying the empty lune property and the so‐called disjoint lunes property is O(nπK). © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract We suggest a novel distance‐based method for the determination of phylogenetic trees. It is based on multidimensional scaling and Euclidean Steiner trees in high‐dimensional spaces. Preliminary computational experience shows that the use of Euclidean Steiner trees for finding phylogenetic trees is a viable approach. Experiments also indicate that the new method is comparable with results produced by neighbor joining (Saitou and Nei, Mol Biol Evol 4 (1987), 406–425). © 2008 Wiley Periodicals, Inc. NETWORKS, 2009