Arrow Research search

Author name cluster

Sebastian Forster

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

SODA Conference 2024 Conference Paper

On Dynamic Graph Algorithms with Predictions

  • Jan van den Brand
  • Sebastian Forster
  • Yasamin Nazari
  • Adam Polak 0001

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. Our first group of results is about partially dynamic problems with edge updates. We give algorithms for incremental and decremental transitive closure and approximate APSP that take as an additional input a predicted sequence of updates (edge insertions, or edge deletions, respectively). They preprocess it in Õ(n (3+ω)/2 ) time, and then handle updates in Õ(1) worst-case time and queries in Õ(n 2 ) worst-case time. Here n is an error measure that can be bounded by the maximum difference between the predicted and actual insertion (deletion) time of an edge, i. e. , by the ℓ ∞ -error of the predictions. The second group of results concerns fully dynamic problems with vertex updates, where the algorithm has access to a predicted sequence of the next n updates. We show how to solve fully dynamic triangle detection, maximum matching, single-source reachability, and more, in O ( n ω-1 + nη i ) worst-case update time. Here η i denotes how much earlier the i -th update occurs than predicted. Our last result is a reduction that transforms a worst-case incremental algorithm without predictions into a fully dynamic algorithm which is given a predicted deletion time for each element at the time of its insertion. As a consequence we can, e. g. , maintain fully dynamic exact APSP with such predictions in Õ(n 2 ) worst-case vertex insertion time and Õ ( n 2 (1 + η i )) worst-case vertex deletion time (for the prediction error η i defined as above). Our algorithms from the first two groups, given sufficiently accurate predictions, achieve running times that go below known lower bounds for classic (without predictions) dynamic algorithms under the OMv Hypothesis. Moreover, our dependence on the prediction errors (so-called smoothness) is conditionally optimal, under plausible fine-grained complexity assumptions, at least in certain parameter regimes. * The full version of the paper can be accessed at https: //arxiv. org/abs/2307. 09961. This work is supported by the Austrian Science Fund (FWF): P 32863-N. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 947702). Part of this work was done when Yasamin Nazari was affiliated with University of Salzburg. Part of this work was done when Adam Polak was affiliated with Max-Planck Institute of Informatics. This work was initiated at the AlgPiE 2022 workshop, organized by IGAFIT. The authors would like to thank Nicole Megow and Danupon Nanongkai for inspiring discussions on algorithms with predictions.

Details

STOC Conference 2023 Conference Paper

Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch

  • Sebastian Forster
  • Yasamin Nazari
  • Maximilian Probst Gutenberg

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 (loglog n ) time.

Details

GandALF Workshop 2023 Workshop Paper

Fast Algorithms for Energy Games in Special Cases

  • Sebastian Forster
  • Antonis Skarlatos
  • Tijn de Vos

In this paper, we study algorithms for special cases of energy games, a class of turn based games on graphs that show up in the quantitative analysis of reactive systems. In an energy game, the vertices of a weighted directed graph belong either to Alice or to Bob. A token is moved to a next vertex by the player controlling its current location, and its energy is changed by the weight of the edge. Given a fixed starting vertex and initial energy, Alice wins the game if the energy of the token remains nonnegative at every moment. If the energy goes below zero at some point, then Bob wins. The problem of determining the winner in an energy game lies in NP intersection coNP. It is a long standing open problem whether a polynomial time algorithm for this problem exists. We devise new algorithms for three special cases of the problem. The first two results focus on the single player version, where either Alice or Bob controls the whole game graph. We develop an tilde O(n^ω W^ω) time algorithm for a game graph controlled by Alice, by providing a reduction to the All Pairs Nonnegative Prefix Paths problem (APNP), where W is the maximum absolute value of any edge weight and ω is the best exponent for matrix multiplication. Thus we study the APNP problem separately, for which we develop an tilde O(n^ω W^ω) time algorithm. For both problems, we improve over the state of the art of tilde O(mn) for small W. For the APNP problem, we also provide a conditional lower bound which states that there is no O(n^(3-ε)) time algorithm for any ε > 0, unless the APSP Hypothesis fails. For a game graph controlled by Bob, we obtain a near linear time algorithm. Regarding our third result, we present a variant of the value iteration algorithm, and we prove that it gives an O(mn) time algorithm for game graphs without negative cycles, which improves a previous upper bound. The all Bob algorithm is randomized, all other algorithms are deterministic.

PDF Details DOI

FOCS Conference 2022 Conference Paper

Fast Deterministic Fully Dynamic Distance Approximation

  • Jan van den Brand
  • Sebastian Forster
  • Yasamin Nazari

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(n 1. 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(n 1. 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(n 1. 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.

Details

SODA Conference 2021 Conference Paper

Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications

  • Sebastian Forster
  • Gramoz Goranci
  • Monika Henzinger

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 (log 4 n ) with update time m 1/2+ o (1) or a tree of expected stretch n o (1) with update time n o (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.

Details

FOCS Conference 2021 Conference Paper

Minor Sparsifiers and the Distributed Laplacian Paradigm

  • Sebastian Forster
  • Gramoz Goranci
  • Yang P. Liu
  • Richard Peng
  • Xiaorui Sun
  • Mingquan Ye

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.

Details

SODA Conference 2020 Conference Paper

Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms

  • Sebastian Forster
  • Danupon Nanongkai
  • Liu Yang
  • Thatchaphol Saranurak
  • Sorrachai Yingchareonthawornchai

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 ( k 2 ν ) time and O ( kν ) queries for the above variant, improving in particular a previous time bound of O ( k O ( 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 + nk 3 ) 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 + n 4/3 k 7/3 ) time [Nanongkai et al. , STOC’19]. The story is the same for directed graphs where our Õ (mk 2 )-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].

Details

STOC Conference 2019 Conference Paper

Dynamic low-stretch trees via dynamic low-diameter decompositions

  • Sebastian Forster
  • Gramoz Goranci

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 n 1/2 + o (1) and the average stretch of the maintained tree is n o (1) , which matches the stretch in the seminal result of Alon et al.

Details

FOCS Conference 2018 Conference Paper

A Faster Distributed Single-Source Shortest Paths Algorithm

  • Sebastian Forster
  • Danupon Nanongkai

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.

Details

SODA Conference 2017 Conference Paper

Fully dynamic all-pairs shortest paths with worst-case update-time revisited

  • Ittai Abraham
  • Shiri Chechik
  • Sebastian Forster

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 ( cn 2 + 2/3 log 4/3 n ) and answers distance queries correctly with probability 1 — 1/n c, 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 Õ ( n 2+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.

Details

STOC Conference 2016 Conference Paper

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

  • Monika Henzinger
  • Sebastian Forster
  • Danupon Nanongkai

We present a deterministic (1+ o (1))-approximation O ( n 1/2+ o (1) + D 1+ 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 Õ( n 1/2 D 1/4 + D )-time algorithm of Nanongkai [STOC 2014] by a factor of as large as n 1/8 , and (ii) the O (є −1 logє −1 )-approximation factor of Lenzen and Patt-Shamir’s Õ( n 1/2+є + D )-time algorithm [STOC 2013] within the same running time. Our running time matches the known time lower bound of Ω( n 1/2 /log n + 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 ( 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 et al. [PODC 2012].

Details

FOCS Conference 2016 Conference Paper

On Fully Dynamic Graph Sparsifiers

  • Ittai Abraham
  • David Durfee
  • Ioannis Koutis
  • Sebastian Forster
  • Richard Peng

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

Details

STOC Conference 2015 Conference Paper

Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture

  • Monika Henzinger
  • Sebastian Forster
  • Danupon Nanongkai
  • Thatchaphol Saranurak

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 v 1 , ..., v n , one by one. After seeing each vector v i , we have to output the product Mv i before we can see the next vector. A naive algorithm can solve this problem using O(n 3 ) time in total, and its running time can be slightly improved to O(n 3 /log 2 n) [Williams SODA'07]. We show that a conjecture that there is no truly subcubic (O(n 3-ε )) 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 conjecture also leads to hardness results for problems that were previously based on diverse problems and conjectures -- such as 3SUM, combinatorial Boolean matrix multiplication, triangle detection, and multiphase -- thus providing a uniform way to prove polynomial hardness results for dynamic algorithms; some of the new proofs are also simpler or even become trivial. The conjecture also leads to stronger and new, non-trivial, hardness results, e.g., for the fully-dynamic densest subgraph and diameter problems.

Details

SODA Conference 2014 Conference Paper

A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths

  • Monika Henzinger
  • Sebastian Forster
  • Danupon Nanongkai

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 ( n 2+ 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 ( n 1. 8+ o (1) + m 1+ o (1) ) while keeping the query time constant. This running time is essentially tight when m = Ω( n 1. 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.

Details

FOCS Conference 2014 Conference Paper

Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time

  • Monika Henzinger
  • Sebastian Forster
  • Danupon Nanongkai

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(n 2+o(1) ) by Bernstein and Roditty (SODA 2011), and more recently to O(n 1. 8+o(1) + m 1+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(m 1+o(1) ) total update time, thus obtaining near-linear time. Moreover, we obtain O(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 log W) time is the O(mn 0. 986 log 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 (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 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.

Details

FOCS Conference 2013 Conference Paper

Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization

  • Monika Henzinger
  • Sebastian Forster
  • Danupon Nanongkai

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(mn 2 ) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n 5/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 = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-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 Ȏ(n 5/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.

Details
v2026.09.13