Graph emulators and hopsets are two fundamental concepts for distance approximation. For a given graph G, an (α,β)-emulator is a sparse graph on the same vertex set that preserves the distances of G up to a multiplicative stretch α and additive stretch β. In contrast, an (α,β)-hopset is a set of additional edges that, when added to G, ensures that distances can be approximated up to a multiplicative stretch α, using paths containing at most β edges. When α = 1+ε for arbitrarily small ε > 0, these structures are known as near-additive emulators and near-exact hopsets, respectively. Prior work showed that there is a remarkable similarity between the constructions and guarantees of these two objects. In their survey on this topic, Elkin and Neiman [Bull. EATCS 130, 2020] explicitly asked whether one can obtain a general reduction between near-additive emulators and near-exact hopsets. Following that, Kogan and Parter [FOCS, 2022] provided a general reduction from hopsets to emulators and spanners. In this paper, we address the reverse direction and show that any construction for a near-additive emulator for undirected unweighted graphs can be leveraged as a black box to construct a hopset for an undirected weighted graph with comparable size, stretch, and a hopbound comparable to the emulator’s additive stretch. Specifically, we show that any algorithm that constructs a (1+ε',β)-emulator, with 0 ≤ ε' ≤ 1 and β ≥ 1, of size S_𝒜(n, ε',β), can be used to obtain a (1+ε, O(β²/ε² ln(n/ε)))-hopset of size O((S_𝒜(n + m β/ε², ε/294, β) 1/ε + n) ln(n/ε)), for any 0 < ε ≤ 1. Therefore, our reduction answers the question of Elkin and Neiman [Bull. EATCS 130, 2020] for sparse graphs and further advances the understanding of the formal connection between these two structures. Designing a reduction resulting in a hopset size that does not depend on m remains an intriguing open question.

Given a weighted undirected graph, a number of clusters k, and an exponent z, the goal in the (k, z)-clustering problem on graphs is to select k vertices as centers that minimize the sum of the distances raised to the power z of each vertex to its closest center. This problem includes the well-known k-median (z = 1) and k-means (z = 2) clustering problems. In the dynamic setting, the graph is subject to adversarial edge updates, and the goal is to maintain explicitly an exact (k, z)-clustering solution in the induced shortest-path metric. Prior works by Bhattacharya, Costa, Garg, Lattanzi, and Parotsidis [FOCS 2024] and by Bhattacharya, Costa, and Farokhnejad [STOC 2025] consider the dynamic (k, z)-clustering problem for point sets in metric spaces. These algorithms support adversarial point insertions and deletions under a model with access to pairwise distances. This model differs significantly from the dynamic graph setting, where no oracle access is given to pairwise distances and a single edge update can affect many distances - making these approaches inefficient when applied to graphs. While efficient dynamic k-center approximation algorithms on graphs exist [Cruciani, Forster, Goranci, Nazari, and Skarlatos, SODA 2024], to the best of our knowledge, no prior work provides similar results for the dynamic (k,z)-clustering problem. As the main result of this paper, we develop a randomized incremental (k, z)-clustering algorithm that maintains with high probability a constant-factor approximation in a graph undergoing edge insertions with a total update time of Õ(k m^{1+o(1)} + k^{1+1/(λ)} m), where λ ≥ 1 is an arbitrary fixed constant. Our incremental algorithm also achieves an amortized update time of Õ(k n^o(1) + k^{1+1/(λ)}) and consists of two stages. In the first stage, we maintain a constant-factor bicriteria approximate solution of size Õ(k) with a total update time of m^{1+o(1)} (independent of the parameter k) over all adversarial edge insertions. This first stage is an intricate adaptation of the bicriteria approximation algorithm by Mettu and Plaxton [Machine Learning 2004] to incremental graphs. One of our key technical results is that the radii in their algorithm can be assumed to be non-decreasing while the approximation ratio remains constant - a property that may be of independent interest. In the second stage, we maintain a constant-factor approximate (k,z)-clustering solution on a dynamic weighted instance induced by the bicriteria approximate solution. For this subproblem, we employ a dynamic spanner algorithm together with a static (k,z)-clustering algorithm.

There has been a surge of interest in spectral hypergraph sparsification, a natural generalization of spectral sparsification for graphs. In this paper, we present a simple fully dynamic algorithm for maintaining spectral hypergraph sparsifiers of directed hypergraphs. Our algorithm achieves a near-optimal size of O(n² / ε ² log ⁷ m) and amortized update time of O(r² log ³ m), where n is the number of vertices, and m and r respectively upper bound the number of hyperedges and the rank of the hypergraph at any time. We also extend our approach to the parallel batch-dynamic setting, where a batch of any k hyperedge insertions or deletions can be processed with O(kr² log ³ m) amortized work and O(log ² m) depth. This constitutes the first spectral-based sparsification algorithm in this setting.

Given points from an arbitrary metric space and a sequence of point updates sent by an adversary, what is the minimum recourse per update (i.e., the minimum number of changes needed to the set of centers after an update), in order to maintain a constant-factor approximation to a k-clustering problem? This question has received attention in recent years under the name consistent clustering.

We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with m edges and n nodes undergoing edge deletions, we provide four new approximate decremental APSP algorithms, two for weighted and two for unweighted graphs. Our first result is (2 + ϵ)-APSP with total update time Õ(m1/2n3/2) (when m = n1+c for any constant 0 < c < 1). Prior to our work the fastest algorithm for weighted graphs with approximation at most 3 had total Õ(mn) update time for (1 + ϵ)-APSP [Bernstein, SICOMP 2016]. Our second result is (2 + ϵ, Wu,v)-APSP with total update time Õ(nm3/4), where the second term is an additive stretch with respect to Wu,v, the maximum weight on the shortest path from u to v. Our third result is (2 + ϵ)-APSP for unweighted graphs in Õ(m7/4) update time, which for sparse graphs (m = o(n8/7)) is the first subquadratic (2 + ϵ)-approximation. Our last result for unweighted graphs is (1 + ϵ, 2(k − 1))-APSP, for k ≥ 2, with Õ(n2−1/km1/k) total update time (when m = n1+c for any constant c > 0). For comparison, in the special case of (1 + ϵ, 2)-approximation, this improves over the state-of-the-art algorithm by [Henzinger, Krinninger, Nanongkai, SICOMP 2016] with total update time of Õ(n2.5). All of our results are randomized, work against an oblivious adversary, and have constant query time.

Dynamic algorithms operate on inputs undergoing updates, e.g., insertions or deletions of edges or vertices. After processing each update, the algorithm has to answer queries regarding the current state of the input data. We study dynamic algorithms in the model of algorithms with predictions (also known as learning-augmented algorithms). We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predictions can be used to improve the running time. In other words, we study the complexity of dynamic problems parameterized by the prediction accuracy. This can be seen as a model interpolating between classic online dynamic algorithms - which know nothing about future updates - and offline dynamic algorithms with the whole update sequence known upfront, which is similar to having perfect predictions. Our results give smooth tradeoffs between these two extreme settings.

In this paper we give the first efficient algorithms for the k-center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into k sets by choosing k centers such that the maximum distance from any data point to its closest center is minimized. It is known that it is NP-hard to get a better than 2 approximation for this problem.

In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for 2-approximate APSP in Õ(n2.5-r + nω(r)) time, for any r ∈ [0,1]. This is O(n2.032) time, using known bounds for rectangular matrix multiplication nω(r) [Le Gall, Urrutia, SODA 2018]. Our result improves on the Õ(n2·25) bound of [Roditty, STOC 2023], and on the bound of [Baswana, Kavitha, SICOMP 2010] for graphs with m ≥ n1·532 edges.

Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the central problems in dynamic graph algorithms. Despite extensive research on this topic, the first result breaking the O(√n) barrier on the update time for any non-trivial approximation was introduced only recently by Forster, Goranci and Henzinger [SODA’21] who achieved m1/ρ+o(1) amortized update time with a O(log n)3ρ−2 factor in the approximation ratio, for any parameter ρ ≥ 1. In this paper, we give the first constant-stretch fully dynamic distance oracle with small polynomial update and query time. Prior work required either at least a poly-logarithmic approximation or much larger update time. Our result gives a more fine-grained trade-off between stretch and update time, for instance we can achieve constant stretch of O(1/ρ2)4/ρ in amortized update time Õ(nρ), and query time Õ(nρ/8) for any constant parameter 0 < ρ < 1. Our algorithm is randomized and assumes an oblivious adversary. A core technical idea underlying our construction is to design a black-box reduction from decremental approximate hub-labeling schemes to fully dynamic distance oracles, which may be of independent interest. We then apply this reduction repeatedly to an existing decremental algorithm to bootstrap our fully dynamic solution.

In this paper, we bring the techniques of the Laplacian paradigm to the congested clique, while further restricting ourselves to deterministic algorithms. In particular, we show how to solve a Laplacian system up to precision ϵ in no(1) log(1/ϵ) rounds. We show how to leverage this result within existing interior point methods for solving flow problems. We obtain an m3/7+o(1) U1/7 round algorithm for maximum flow on a weighted directed graph with maximum weight U, and we obtain an Õ(m3/7(n0.158 + no(1) poly log W)) round algorithm for unit capacity minimum cost flow on a directed graph with maximum cost W. Hereto, we give a novel routine for computing Eulerian orientations in O(log n log* n) rounds, which we believe may be of separate interest.

We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update time and answers queries for the distance between any pair of vertices in the current graph with a polylogarithmic approximation in O(loglogn) time.

Abstract A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $$(1\pm \epsilon )$$ ( 1 ± ϵ ) . This paper considers computing cut sparsifiers of weighted graphs of size $$O(n\log (n)/\epsilon ^2)$$ O ( n log ( n ) / ϵ 2 ) . Our algorithm computes such a sparsifier in time $$O(m\cdot \min (\alpha (n)\log (m/n),\log (n)))$$ O ( m · min ( α ( n ) log ( m / n ) , log ( n ) ) ) , both for graphs with polynomially bounded and unbounded integer weights, where $$\alpha (\cdot )$$ α ( · ) is the functional inverse of Ackermann’s function. This improves upon the state of the art by Benczúr and Karger (SICOMP, 2015), which takes $$O(m\log ^2 (n))$$ O ( m log 2 ( n ) ) time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP, 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi–Ibaraki forest packing. MSF packings have previously been used by Abraham et al. (FOCS, 2016) in the dynamic setting, and are defined as follows: an M-partial MSF packing of G is a set $$\mathcal {F}=\{F_1, \ldots , F_M\}$$ F = { F 1 , … , F M } , where $$F_i$$ F i is a maximum spanning forest in $$G{\setminus } \bigcup _{j=1}^{i-1}F_j$$ G \ ⋃ j = 1 i - 1 F j . Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain improved dynamic algorithms that, given an unweighted and undirected graph G = (V, E) undergoing edge insertions and deletions, and a parameter $0 \lt \epsilon \leq 1$, maintain (1 + ϵ)-approximations of the st-distance between a given pair of nodes s and t, the distances from a single source to all nodes (“SSSP”), the distances from multiple sources to all nodes (“MSSP”), or the distances between all nodes (“APSP”). Our main result is a deterministic algorithm for maintaining (1 + ϵ)-approximate st-distance with worst-case update time O(n1.407) (for the current best known bound on the matrix multiplication exponent (ω). This even improves upon the fastest known randomized algorithm for this problem. Similar to several other well-studied dynamic problems whose state-of-the-art worst-case update time is O(n1.407), this matches a conditional lower bound [BNS, FOCS 2019]. We further give a deterministic algorithm for maintaining (1 + ϵ)-approximate single-source distances with worst-case update time O(n1.529), which also matches a conditional lower bound. At the core, our approach is to combine algebraic distance maintenance data structures with near-additive emulator constructions. This also leads to novel dynamic algorithms for maintaining (1 + ϵ, β)-emulators that improve upon the state of the art, which might be of independent interest. Our techniques also lead to improved randomized algorithms for several problems such as exact st-distances and diameter approximation.

A cut sparsifier is a reweighted subgraph that maintains the weights of the cuts of the original graph up to a multiplicative factor of $(1\pmε)$. This paper considers computing cut sparsifiers of weighted graphs of size $O(n\log (n)/ε^2)$. Our algorithm computes such a sparsifier in time $O(m\cdot\min(α(n)\log(m/n),\log (n)))$, both for graphs with polynomially bounded and unbounded integer weights, where $α(\cdot)$ is the functional inverse of Ackermann's function. This improves upon the state of the art by Benczúr and Karger (SICOMP 2015), which takes $O(m\log^2 (n))$ time. For unbounded weights, this directly gives the best known result for cut sparsification. Together with preprocessing by an algorithm of Fung et al. (SICOMP 2019), this also gives the best known result for polynomially-weighted graphs. Consequently, this implies the fastest approximate min-cut algorithm, both for graphs with polynomial and unbounded weights. In particular, we show that it is possible to adapt the state of the art algorithm of Fung et al. for unweighted graphs to weighted graphs, by letting the partial maximum spanning forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest packing. MSF packings have previously been used by Abraham at al. (FOCS 2016) in the dynamic setting, and are defined as follows: an $M$-partial MSF packing of $G$ is a set $\mathcal{F}=\{F_1, \dots, F_M\}$, where $F_i$ is a maximum spanning forest in $G\setminus \bigcup_{j=1}^{i-1}F_j$. Our method for computing (a sufficient estimation of) the MSF packing is the bottleneck in the running time of our sparsification algorithm.

In this paper, we bring the main tools of the Laplacian paradigm to the Broadcast Congested Clique. We introduce an algorithm to compute spectral sparsifiers in a polylogarithmic number of rounds, which directly leads to an efficient Laplacian solver. Based on this primitive, we consider the linear program solver of Lee and Sidford [30].

We study distributed algorithms built around minor-based vertex sparsifiers, and give the first algorithm in the CONGEST model for solving linear systems in graph Laplacian matrices to high accuracy. Our Laplacian solver has a round complexity of$O(n^{o(1)}(\sqrt{n}+D))$, and thus almost matches the lower bound of$\widetilde{\Omega}(\sqrt{n}+D)$, where$n$is the number of nodes in the network and$D$is its diameter. We show that our distributed solver yields new sublinear round algorithms for several cornerstone problems in combinatorial optimization. This is achieved by leveraging the powerful algorithmic framework of Interior Point Methods (IPMs) and the Laplacian paradigm in the context of distributed graph algorithms, which entails numerically solving optimization problems on graphs via a series of Laplacian systems. Problems that benefit from our distributed algorithmic paradigm include exact mincost flow, negative weight shortest paths, maxflow, and bipartite matching on sparse directed graphs. For the maxflow problem, this is the first exact distributed algorithm that applies to directed graphs, while the previous work by [Ghaffari et al. SICOMP'18] considered the approximate setting and works only for undirected graphs. For the mincost flow and the negative weight shortest path problems, our results constitute the first exact distributed algorithms running in a sublinear number of rounds. Given that the hybrid between IPMs and the Laplacian paradigm has proven useful for tackling numerous optimization problems in the centralized setting, we believe that our distributed solver will find future applications. At the heart of our distributed Laplacian solver is the notion of spectral subspace sparsifiers of [Li, Schild FOCS'18]. We present a nontrivial distributed implementation of their construction by (i) giving a parallel variant of their algorithm that avoids the sampling of random spanning trees and uses approximate leverage scores instead, and (ii) showing that the algorithm still produces a high-quality subspace spectral sparsifier by carefully setting up and analyzing matrix martingales. Combining this vertex reduction recursively with both tree and elimination-based preconditioners leads to our algorithm for solving Laplacian systems. The construction of the elimination-based preconditioners is based on computing short random walks, and we introduce a new technique for reducing the congestion incurred by the simulation of these walks on weighted graphs.

Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter and there are relatively few spanner edges between clusters. In this paper, we provide a clustering algorithm that, given $k\geq 2$, can be used to compute a spanner of stretch $2k-1$ and expected size $O(n^{1+1/k})$ in $k$ rounds in the CONGEST model. This improves upon the state of the art (by Elkin, and Neiman [TALG'19]) by making the bounds on both running time and stretch independent of the random choices of the algorithm, whereas they only hold with high probability in previous results. Spanners are used in certain synchronizers, thus our improvement directly carries over to such synchronizers. Furthermore, for keeping the \emph{total} number of inter-cluster edges small in low diameter decompositions, our clustering algorithm provides the following guarantees. Given $β\in (0,1]$, we compute a low diameter decomposition with diameter bound $O\left(\frac{\log n}β\right)$ such that each edge $e\in E$ is an inter-cluster edge with probability at most $β\cdot w(e)$ in $O\left(\frac{\log n}β\right)$ rounds in the CONGEST model. Again, this improves upon the state of the art (by Miller, Peng, and Xu [SPAA'13]) by making the bounds on both running time and diameter independent of the random choices of the algorithm, whereas they only hold with high probability in previous results.

We give the first non-trivial fully dynamic probabilistic tree embedding algorithm for a weighted, undirected graph G with n nodes and at most m edges undergoing edge insertions and deletions. The goal in this problem is to maintain a tree containing all nodes of G with a randomized algorithm such that for every edge (u, v) of G the expected length of the path from u to v in the tree exceeds the weight of the edge (u, v) only by a small multiplicative factor, called the stretch of the embedding. In this paper, we obtain a trade-off between amortized update time and expected stretch against an oblivious adversary. At the two extremes of this trade-off, we can maintain a tree of expected stretch O(log4 n) with update time m1/2+o(1) or a tree of expected stretch no(1) with update time no(1) (for edge weights polynomial in n). A guarantee of the latter type has so far only been known for maintaining tree embeddings with average (instead of expected) stretch [Chechik/Zhang, SODA '20]. Our main result has direct implications to fully dynamic approximate distance oracles and fully dynamic buy-at-bulk network design as our trade-off from above carries over to these two problems with minor overheads. For dynamic distance oracles, our result is the first to break the update-time barrier. For buy-at-bulk network design, a problem which also in the static setting heavily relies on probabilistic tree embeddings, we give the first non-trivial dynamic algorithm. As probabilistic tree embeddings are an important tool in static approximation algorithms, we expect our result to have further applications in dynamic approximation algorithms. From a technical perspective, we obtain our main result by first designing a decremental (i.e., deletionsonly) algorithm for probabilistic low-diameter decompositions via a careful combination of Bartal's ball-growing approach [FOCS ‘96] with the pruning framework of Chechik and Zhang [SODA ‘20]. Such a low-diameter decomposition is the heart of Bartal's seminal tree embedding construction and we show how to adapt it to the decremental setting. We then extend this to a fully dynamic algorithm by significantly enriching a well-known “decremental to fully dynamic” reduction with a new bootstrapping idea to recursively employ a fully dynamic algorithm instead of a static one in this reduction. By additionally exploiting certain properties of our tree embedding, this bootstrapping scheme can be made highly efficient.

We present a method for solving the transshipment problem-also known as uncapacitated minimum cost flow-up to a multiplicative error of 1+ε in undirected graphs with nonnegative edge weights using a tailored gradient descent algorithm. Using O(\cdot ) to hide polylogarithmic factors in n (the number of nodes in the graph), our gradient descent algorithm takes O(ε 2) iterations, and in each iteration it solves an instance of the transshipment problem up to a multiplicative error of polylog n. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a randomized rounding scheme, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve upon prior works by obtaining the following results: (1) Broadcast CONGEST model: (1 + ε)-approximate SSSP using O(( n + D)ε 3) rounds, where D is the (hop) diameter of the network. (2) Broadcast Congested Clique model: (1 + ε)-approximate transshipment and SSSP using O (ε 2) rounds. (3) Multipass Streaming model: (1 + ε)-approximate transshipment and SSSP using O(n) space and O(ε 2) passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume nonnegative edge weights that are polynomially bounded in n; for general nonnegative weights, there is an additional multiplicative overhead equal to the logarithm of the maximum ratio between nonzero weights. Our algorithms can also handle asymmetric costs for traversing edges in opposite directions. In this case, we obtain an additional multiplicative dependence of the maximum ratio between the two costs on some edge.

We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \sf CONGEST model); here $n$ is the number of nodes in the network, $D$ is its (hop) diameter, and edge weights are positive integers from 1 to $\operatorname{poly}(n)$. This is the first nontrivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized $(1+o(1))$-approximation $\tilde{O}(\sqrt{n}D^{1/4}+D)$-time algorithm of Nanongkai [in Proceedings of STOC, 2014, pp. 565--573] by a factor of as large as $n^{1/8}$, and (ii) the $O(\epsilon^{-1}\log\epsilon^{-1})$-approximation factor of Lenzen and Patt-Shamir's $\tilde{O}(n^{1/2+\epsilon}+D)$-time algorithm [in Proceedings of STOC, 2013, pp. 381--390] within the same running time. (Throughout, we use $\tilde{O}(\cdot)$ to hide polylogarithmic factors in $n$.) Our running time matches the known time lower bound of $\Omega(\sqrt{n/\log n}+D)$ [M. Elkin, SIAM J. Comput., 36 (2006), pp. 433--456], thus essentially settling the status of this problem which was raised at least a decade ago [M. Elkin, SIGACT News, 35 (2004), pp. 40--57]. It also implies a $(2+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for approximating a network's weighted diameter which almost matches the lower bound by Holzer and Pinsker [in Proceedings of OPODIS, 2015, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Germany, 2016, 6]. In achieving this result, we develop two techniques which might be of independent interest and useful in other settings: (i) a deterministic process that replaces the “hitting set argument” commonly used for shortest paths computation in various settings, and (ii) a simple, deterministic construction of an $(n^{o(1)},o(1))$-hop set of size $n^{1+o(1)}$. We combine these techniques with many distributed algorithmic techniques, some of which are from problems that are not directly related to shortest paths, e.g., ruling sets [A. V. Goldberg, S. A. Plotkin, and G. E. Shannon, SIAM J. Discrete Math., 1 (1988), pp. 434--446], source detection [C. Lenzen and D. Peleg, in Proceedings of PODC, 2013, pp. 375--382], and partial distance estimation [C. Lenzen and B. Patt-Shamir, in Proceedings of PODC, 2015, pp. 153--162]. Our hop set construction also leads to single-source shortest paths algorithms in two other settings: (i) a $(1+o(1))$-approximation $n^{o(1)}$-time algorithm on congested cliques, and (ii) a $(1+o(1))$-approximation $n^{o(1)}$-pass $n^{1+o(1)}$-space streaming algorithm. The first result answers an open problem in [D. Nanongkai, in Proceedings of STOC, 2014, pp. 565--573]. The second result partially answers an open problem raised by McGregor in 2006 [ List of Open Problems in Sublinear Algorithms: Problem 14].

Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas) and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this article, we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. (1) For dynamic spanner, the only known o ( n ) worst-case bounds were O ( n 3/4 ) high-probability worst-case update time for maintaining a 3-spanner and O ( n 5/9 ) for maintaining a 5-spanner. We give a O (1) k log 3 ( n ) high-probability worst-case time bound for maintaining a ( 2k-1 )-spanner, which yields the first worst-case polylog update time for all constant k . (All the results above maintain the optimal tradeoff of stretch 2k-1 and Õ( n 1+1/k ) edges.) (2) For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O (log 5 ( n )) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2+ϵ)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: An algorithm is said to have worst-case expected update time ɑ if for every update σ, the expected time to process σ is at most ɑ. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: A worst-case expected update time of O(1) still allows for the possibility that every 1/ f(n) updates requires ϴ ( f(n) ) time to process, for arbitrarily high f(n) . In this article, we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: The query time remains the same, while the update time increases by a factor of O (log 2(n) ). Thus, we achieve our results in two steps: (1) First, we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then, we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.

Consider the following “local” cut-detection problem in a directed graph: We are given a seed vertex x and need to remove at most k edges so that at most v edges can be reached from x (a “local” cut) or output ⊥ to indicate that no such cut exists. If we are given query access to the input graph, then this problem can in principle be solved without reading the whole graph and with query complexity depending on k and ν. In this paper we consider a slack variant of this problem where, when such a cut exists, we can output a cut with up to O(kν) edges reachable from x. We present a simple randomized algorithm spending O(k2ν) time and O(kν) queries for the above variant, improving in particular a previous time bound of O(kO(k)ν) by Chechik et al. [SODA’17]. We also extend our algorithm to handle an approximate variant. We demonstrate that these local algorithms are versatile primitives for designing substantially improved algorithms for classic graph problems by providing the following three applications. (Throughout, Õ(T) hides polylog(T).) A randomized algorithm for the classic k-vertex connectivity problem that takes near-linear time when k = O(polylog(n)), namely Õ(m + nk3) time in undirected graphs. Prior to our work, the state of the art for this range of k were linear-time algorithms for k ≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73] and a recent algorithm with Õ(m + n4/3k7/3) time [Nanongkai et al., STOC’19]. The story is the same for directed graphs where our Õ(mk2)-time algorithm is near-linear when k = O(polylog(n)). Our techniques also yield an improved approximation scheme. Property testing algorithms for k-edge and -vertex connectivity with query complexities that are near-linear in k, exponentially improving the state-of-the-art. This resolves two open problems, one by Goldreich and Ron [STOC’97] and one by Orenstein and Ron [Theor. Comput. Sci.’11]. A faster algorithm for computing the maximal k-edge connected subgraphs, improving prior work of Chechik et al. [SODA’17].

Many dynamic graph algorithms have an amortized update time, rather than a stronger worst-case guarantee. But amortized data structures are not suitable for real-time systems, where each individual operation has to be executed quickly. For this reason, there exist many recent randomized results that aim to provide a guarantee stronger than amortized expected. The strongest possible guarantee for a randomized algorithm is that it is always correct (Las Vegas), and has high-probability worst-case update time, which gives a bound on the time for each individual operation that holds with high probability. In this paper we present the first polylogarithmic high-probability worst-case time bounds for the dynamic spanner and the dynamic maximal matching problem. 1. For dynamic spanner, the only known o(n) worst-case bounds were O(n3/4) high-probability worst-case update time for maintaining a 3-spanner, and O(n5/9) for maintaining a 5-spanner. We give a O(1)k log3(n) high-probability worst-case time bound for maintaining a (2k – 1)-spanner, which yields the first worst-case polylog update time for all constant k. (All the results above maintain the optimal tradeoff of stretch 2k – 1 and Õ(n1+1/k) edges.) 2. For dynamic maximal matching, or dynamic 2-approximate maximum matching, no algorithm with o(n) worst-case time bound was known and we present an algorithm with O(log5 (n)) high-probability worst-case time; similar worst-case bounds existed only for maintaining a matching that was (2 + ∊)-approximate, and hence not maximal. Our results are achieved using a new approach for converting amortized guarantees to worst-case ones for randomized data structures by going through a third type of guarantee, which is a middle ground between the two above: an algorithm is said to have worst-case expected update time α if for every update σ, the expected time to process σ is at most α. Although stronger than amortized expected, the worst-case expected guarantee does not resolve the fundamental problem of amortization: a worst-case expected update time of O(1) still allows for the possibility that every 1/f(n) updates requires Θ(f(n)) time to process, for arbitrarily high f(n). In this paper we present a black-box reduction that converts any data structure with worst-case expected update time into one with a high-probability worst-case update time: the query time remains the same, while the update time increases by a factor of O(log2(n)). Thus we achieve our results in two steps: (1) First we show how to convert existing dynamic graph algorithms with amortized expected polylogarithmic running times into algorithms with worst-case expected polylogarithmic running times. (2) Then we use our black-box reduction to achieve the polylogarithmic high-probability worst-case time bound. All our algorithms are Las-Vegas-type algorithms.

Spanning trees of low average stretch on the non-tree edges, as introduced by Alon et al. [SICOMP 1995], are a natural graph-theoretic object. In recent years, they have found significant applications in solvers for symmetric diagonally dominant (SDD) linear systems. In this work, we provide the first dynamic algorithm for maintaining such trees under edge insertions and deletions to the input graph. Our algorithm has update time n1/2 + o(1) and the average stretch of the maintained tree is no(1) , which matches the stretch in the seminal result of Alon et al.

We devise new algorithms for the single-source shortest paths (SSSP) problem with non-negative edge weights in the CONGEST model of distributed computing. While close-to-optimal solutions, in terms of the number of rounds spent by the algorithm, have recently been developed for computing SSSP approximately, the fastest known exact algorithms are still far away from matching the lower bound of Ω (n + D) rounds by Peleg and Rubinovich [SIAM Journal on Computing 2000], where n is the number of nodes in the network and D is its diameter. The state of the art is Elkin's randomized algorithm [STOC 2017] that performs Õ(n^2/3 D^1/3 + n^5/6) rounds. We significantly improve upon this upper bound with our two new randomized algorithms for polynomially bounded integer edge weights, the first performing Õ(√n D) rounds and the second performing Õ(√n D^1/4 + n^3/5 + D) rounds. Our bounds also compare favorably to the independent result by Ghaffari and Li [STOC 2018]. As side results, we obtain a (1+ε)-approximation Õ((√n D^1/4+D)/ε)-round algorithm for directed SSSP and a new work/depth trade-off for exact SSSP on directed graphs in the PRAM model.

In the decremental single-source shortest paths (SSSP) problem, we want to maintain the distances between a given source node s and every other node in an n -node m -edge graph G undergoing edge deletions. While its static counterpart can be solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O ( mn ) total update time of Even and Shiloach [16] has been the fastest known algorithm for three decades. At the cost of a (1+ϵ)-approximation factor, the running time was recently improved to n 2+ o (1) by Bernstein and Roditty [9]. In this article, we bring the running time down to near-linear: We give a (1+ϵ)-approximation algorithm with m 1+ o (1) expected total update time, thus obtaining near-linear time . Moreover, we obtain m 1+ o (1) log W time for the weighted case, where the edge weights are integers from 1 to W . The only prior work on weighted graphs in o ( mn ) time is the mn 0.9 + o (1) -time algorithm by Henzinger et al. [18, 19], which works for directed graphs with quasi-polynomial edge weights. The expected running time bound of our algorithm holds against an oblivious adversary. In contrast to the previous results, which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse ( h , ϵ )- hop set introduced by Cohen [12] in the PRAM literature. An ( h , ϵ)-hop set of a graph G =( V , E ) is a set F of weighted edges such that the distance between any pair of nodes in G can be (1+ϵ)-approximated by their h -hop distance (given by a path containing at most h edges) on G ′ =( V , E ∪ F ). Our algorithm can maintain an ( n o (1) , ϵ)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain approximate distances using this hop set, we extend the monotone Even-Shiloach tree of Henzinger et al. [20] and combine it with the bounded-hop SSSP technique of Bernstein [4, 5] and Mądry [27]. These two new tools might be of independent interest.

We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with n nodes and m edges. This problem has a long history in combinatorial optimization and has recently seen interesting applications in the context of quantitative verification. We focus on strongly polynomial algorithms to cover the use-case where the weights are relatively large compared to the size of the graph. Our main result is an algorithm with running time ~O(m^{3/4} n^{3/2}), which gives the first improvement over Megiddo's ~O(n^3) algorithm [JACM'83] for sparse graphs (We use the notation ~O(.) to hide factors that are polylogarithmic in n.) We further demonstrate how to obtain both an algorithm with running time n^3/2^{Omega(sqrt(log n)} on general graphs and an algorithm with running time ~O(n) on constant treewidth graphs. To obtain our main result, we develop a parallel algorithm for negative cycle detection and single-source shortest paths that might be of independent interest.

We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repertoire of connectivity queries. Our main technical contribution is a decremental data structure that supports sensitivity queries of the form "are u and v strongly connected in the graph G \ w?", for any triple of vertices u, v, w, while G undergoes deletions of edges. Our data structure processes a sequence of edge deletions in a digraph with $n$ vertices in O(m n log n) total time and O(n^2 log n) space, where m is the number of edges before any deletion, and answers the above queries in constant time. We can leverage our data structure to obtain decremental data structures for many more types of queries within the same time and space complexity. For instance for edge-related queries, such as testing whether two query vertices u and v are strongly connected in G \ e, for some query edge e. As another important application of our decremental data structure, we provide the first nontrivial algorithm for maintaining the dominator tree of a flow graph under edge deletions. We present an algorithm that processes a sequence of edge deletions in a flow graph in O(m n log n) total time and O(n^2 log n) space. For reducible flow graphs we provide an O(mn)-time and O(m + n)-space algorithm. We give a conditional lower bound that provides evidence that these running times may be tight up to subpolynomial factors.

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

We present a method for solving the shortest transshipment problem-also known as uncapacitated minimum cost flow-up to a multiplicative error of 1 + ε in undirected graphs with non-negative integer edge weights using a tailored gradient descent algorithm. Our gradient descent algorithm takes ε-3 polylog n iterations, and in each iteration it needs to solve an instance of the transshipment problem up to a multiplicative error of polylog n, where n is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. Using a careful white-box analysis, we can further extend the method to finding approximate solutions for the single-source shortest paths (SSSP) problem. As a consequence, we improve prior work by obtaining the following results: 1. Broadcast CONGEST model: (1+")-approximate SSSP using Õ((√ n+D) · ε-O(1)) rounds, 1 where D is the (hop) diameter of the network. 2. Broadcast congested clique model: (1+ε)-approximate shortest transshipment and SSSP using Õ (ε-O(1)) rounds. 3. Multipass streaming model: (1+ε)-approximate shortest transshipment and SSSP using Õ (n) space and Õ(ε-O(1)) passes. The previously fastest SSSP algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in n; for general nonnegative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs for traversing an edge in opposite directions, running times scale with the maximum ratio between the costs of both directions over all edges.

We revisit the hardness of approximating the diameter of a network. In the CONGEST model, ~Omega(n) rounds are necessary to compute the diameter [Frischknecht et al. SODA'12]. Abboud et al. [DISC 2016] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer 1 <= l <= polylog(n) , distinguishing between networks of diameter 4l + 2 and 6l + 1 requires ~Omega(n) rounds. We slightly tighten this result by showing that even distinguishing between diameter 2l + 1 and 3l + 1 requires ~Omega(n) rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition. This is suited for teaching both the lower bound in the CONGEST model and the conditional lower bound in the RAM model.

We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic (1+ϵ)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D , the maximum diameter of the network. Our technique also leads to a deterministic (1+ϵ)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011; Henzinger et al. 2015). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed.

An $α$-spanner of a graph $ G $ is a subgraph $ H $ such that $ H $ preserves all distances of $ G $ within a factor of $ α$. In this paper, we give fully dynamic algorithms for maintaining a spanner $ H $ of a graph $ G $ undergoing edge insertions and deletions with worst-case guarantees on the running time after each update. In particular, our algorithms maintain: (1) a $3$-spanner with $ \tilde O (n^{1+1/2}) $ edges with worst-case update time $ \tilde O (n^{3/4}) $, or (2) a $5$-spanner with $ \tilde O (n^{1+1/3}) $ edges with worst-case update time $ \tilde O (n^{5/9}) $. These size/stretch tradeoffs are best possible (up to logarithmic factors). They can be extended to the weighted setting at very minor cost. Our algorithms are randomized and correct with high probability against an oblivious adversary. We also further extend our techniques to construct a $5$-spanner with suboptimal size/stretch tradeoff, but improved worst-case update time. To the best of our knowledge, these are the first dynamic spanner algorithms with sublinear worst-case update time guarantees. Since it is known how to maintain a spanner using small amortized but large worst-case update time [Baswana et al. SODA'08], obtaining algorithms with strong worst-case bounds, as presented in this paper, seems to be the next natural step for this problem.

We initiate the study of fast dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-spectral sparsifier with amortized update time poly(log n, ϵ-1). Second, we give a fully dynamic algorithm for maintaining a (1 ± ϵ)-cut sparsifier with worst-case update time poly(log n, ϵ-1). Both sparsifiers have size n · poly(log n, ϵ-1). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a (1 - ϵ)-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time poly(log n, ϵ-1).

We present a deterministic (1+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the CONGEST model); here n is the number of nodes in the network and D is its (hop) diameter. This is the first non-trivial deterministic algorithm for this problem. It also improves (i) the running time of the randomized (1+o(1))-approximation Õ(n1/2D1/4+D)-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n1/8, and (ii) the O(є−1logє−1)-approximation factor of Lenzen and Patt-Shamir’s Õ(n1/2+є+D)-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω(n1/2/logn + D) [Das Sarma et al. STOC 2011] modulo some lower-order terms, thus essentially settling the status of this problem which was raised at least a decade ago [Elkin SIGACT News 2004]. It also implies a (2+o(1))-approximation O(n1/2+o(1)+D1+o(1))-time algorithm for approximating a network’s weighted diameter which almost matches the lower bound by Holzer et al. [PODC 2012].

We study dynamic $(1+\epsilon)$-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected $n$-node $m$-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of $\tilde O(mn/\epsilon)$ and constant query time by Roditty and Zwick [SIAM J. Comput., 41 (2012), pp. 670--683]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [J. ACM, 28 (1981), pp. 1--4]; it has a total update time of $O(mn^2)$ and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of $\tilde O(n^{5/2}/\epsilon)$ and constant query time that has an additive error of 2 in addition to the $1+\epsilon$ multiplicative error. This beats the previous $\tilde O(mn/\epsilon)$ time when $m=\Omega(n^{3/2})$. Note that the additive error is unavoidable since, even in the static case, an $O(n^{3-\delta})$-time (a so-called truly subcubic) combinatorial algorithm with $1+\epsilon$ multiplicative error cannot have an additive error less than $2-\epsilon$, unless we make a major breakthrough for Boolean matrix multiplication [D. Dor, S. Halrepin, and U. Zwick, SIAM J. Comput., 29 (2000), pp. 1740--1759] and many other long-standing problems [V. Vassilevska Williams and R. Williams, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 645--654]. The algorithm can also be turned into a $(2+\epsilon)$-approximation algorithm (without an additive error) with the same time guarantees, improving the recent $(3+\epsilon)$-approximation algorithm with $\tilde O(n^{5/2+O(\sqrt{\log{(1/\epsilon)} / \log n})})$ running time of Bernstein and Roditty [Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1355--1365] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of $\tilde O(mn/\epsilon)$ and a query time of $O(\log\log n)$. The algorithm has a multiplicative error of $1+\epsilon $ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in [Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, 2013, pp. 725--734]. The deterministic algorithm can be turned into a deterministic fully dynamic $ (1+\epsilon) $-approximation with an amortized update time of $ \tilde O (m n / (\epsilon t))$ and a query time of $ \tilde O (t) $ for every $ t \leq \sqrt{n} $. In order to achieve our results, we introduce two new techniques: (i) A monotone Even--Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called a locally persevering emulator. (ii) A derandomization technique based on moving Even--Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.

Consider the following Online Boolean Matrix-Vector Multiplication problem: We are given an n x n matrix M and will receive n column-vectors of size n, denoted by v1, ..., vn, one by one. After seeing each vector vi, we have to output the product Mvi before we can see the next vector. A naive algorithm can solve this problem using O(n3) time in total, and its running time can be slightly improved to O(n3/log2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n3-ε)) time algorithm for this problem can be used to exhibit the underlying polynomial time hardness shared by many dynamic problems. For a number of problems, such as subgraph connectivity, Pagh's problem, d-failure connectivity, decremental single-source shortest paths, and decremental transitive closure, this conjecture implies tight hardness results. Thus, proving or disproving this conjecture will be very interesting as it will either imply several tight unconditional lower bounds or break through a common barrier that blocks progress with these problems. This conjecture might also be considered as strong evidence against any further improvement for these problems since refuting it will imply a major breakthrough for combinatorial Boolean matrix multiplication and other long-standing problems if the term "combinatorial algorithms" is interpreted as "Strassen-like algorithms" [Ballard et al. SPAA'11].

The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach (JACM 1981) has been the fastest known algorithm for three decades. With the loss of a (1 + ε)-approximation factor, the running time was recently improved to O(n2+o(1)) by Bernstein and Roditty (SODA 2011), and more recently to O(n1.8+o(1)+ m1+o(1)) by Henzinger, Krinninger, and Nanongkai (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1 + ε)-approximation algorithm with O(m1+o(1)) total update time, thus obtaining near-linear time. Moreover, we obtain O(m1+o(1)log W) time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn log W) time is the O(mn0.986log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, ε)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, ε)-hop set of a graph G = (V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1 + ε)-approximated by their d-hop distance (given by a path containing at most d edges) on G'=(V, E∪E'). Our algorithm can maintain an (no(1), ε)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach tree. It results from extending and combining the monotone Even-Shiloach tree of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP technique of Bernstein (STOC 2013). These two new tools might be of independent interest.

We study dynamic (1 + ∊)-approximation algorithms for the single-source shortest paths problem in an unweighted undirected n-node m-edge graph under edge deletions. The fastest algorithm for this problem is an algorithm with O(n2+o(1)) total update time and constant query time by Bernstein and Roditty (SODA 2011). In this paper, we improve the total update time to O(n1.8+o(1) + m1+o(1)) while keeping the query time constant. This running time is essentially tight when m = Ω(n1.8) since we need Ω(m) time even in the static setting. For smaller values of m, the running time of our algorithm is subquadratic, and is the first that breaks through the quadratic time barrier. In obtaining this result, we develop a fast algorithm for what we call center cover data structure. We also make non-trivial extensions to our previous techniques called lazy-update and monotone Even-Shiloach trees (ICALP 2013 and FOCS 2013). As by-products of our new techniques, we obtain two new results for the decremental all-pairs shortest-paths problem. Our first result is the first approximation algorithm whose total update time is faster than Õ(mn) for all values of m. Our second result is a new trade-off between the total update time and the additive approximation guarantee.

We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem.

We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn2) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n5/2) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = Ω(n3/2). Note that the additive error is unavoidable since, even in the static case, an O(n3-δ)-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n5/2+O(1√(log n))) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.

In this paper, a new technique for online signature verification or identification is proposed. The technique integrates a longest common subsequences (LCSS) detection algorithm which measures the similarity of signature time series into a kernel function for support vector machines (SVM). LCSS offers the possibility to consider the local variability of signals such as the time series of pen-tip coordinates on a graphic tablet, forces on a pen, or inclination angles of a pen measured during a signing process. Consequently, the similarity of two signature time series can be determined in a more reliable way than with other measures. A proprietary database with signatures of 153 test persons and the SVC 2004 benchmark database are used to show the properties of the new SVM-LCSS. We investigate its parameterization and compare it to SVM with other kernel functions such as dynamic time warping (DTW). Our experiments show that SVM with the LCSS kernel authenticate persons very reliably and with a performance which is significantly better than that of the best comparing technique, SVM with DTW kernel.