Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs

Maximilian Probst Gutenberg

supervised by

Christian Wulff-Nilsen and Mikkel Thorup

This thesis has been submitted to the PhD School of The Faculty of Science,

University of Copenhagen

September, 2020

Thesis Title:     Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs

Author:     Maximilian Probst Gutenberg

Affiliation:     University of Copenhagen, Faculty of Science, Department of Computer Science (DIKU) and Basic Algorithm Research Center (BARC).

Advisors:     Christian Wulff-Nilsen (DIKU and BARC) and Mikkel Thorup (DIKU and BARC)

Thesis Committee:     Valerie King (University of Victoria), Jakob Nordström (DIKU and Lund University), Uri Zwick (Tel Aviv University)

Date of Submission:     September, 2020

To my wife, Johanna.

§ ABSTRACT

In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions:

* Single-Source Reachability (SSR): given a distinct source vertex $r$ in a graph, the objective is to maintain the set of vertices that $r$ can reach throughout the entire update sequence.

* Strongly-Connected Components (SCC): the goal is to maintain a partition of the vertex set $X_1, X_2, \dots, X_k$, such that every two vertices in the same partition set $X_i$ are on a common cycle, while no two vertices across different partition sets do.

* Single-Source Shortest Paths (SSSP): given a dedicated source vertex $s$, the objective is to maintain the distance from $s$ to every other vertex in the graph.

These problems have recently received an extraordinary amount of attention due to their role as subproblems in various more complex and notoriously hard graph problems, especially to compute flows, bipartite matchings and cuts.

Our techniques lead to the first near-optimal data structures for these problems in various different settings. Letting $n$ denote the number of vertices in the graph and by $m$ the maximum number of edges in any version of the graph, we obtain

* the first randomized data structure to maintain SSR and SCCs in near-optimal total update time $\tilde{O}(m)$ in a graph undergoing edge deletions.

* the first randomized data structure to maintain SSSP in partially dynamic graphs in total update time $\tilde{O}(n^2)$ which is near-optimal in dense graphs.

* the first deterministic data structures for SSR and SCC for graphs undergoing edge deletions, and for SSSP in partially dynamic graphs that improve upon the $O(mn)$ total update time by Even and Shiloach from 1981 that is often considered to be a fundamental barrier.

§ ABSTRAKT

I denne afhandling præsenterer vi nye teknikker til at håndtere grundlæggende algoritmiske grafteoretiske problemer, hvor grafer er orienterede og delvist dynamiske, dvs. enten gennemgår en sekvens af kantindsættelser eller sletninger:

* Single-Source Reachability (SSR): Givet en særskilt kilde $r$ i en graf, er målet at opretholde et mængde af de knuder, $r$ kan nå gennem hele opdateringssekvensen.

* Strongly-Connected Components (SCC): Målet er at opretholde en partition af knudemængder $ X_1, X_2, \dots, X_k $, således at hvert par af knuder i samme partitionssæt $ X_i $ er på en fælles kreds, mens intet par af knuder i forskellige partitionsmængder har denne egenskab.

* Single-Source Shortest Paths (SSSP): Givet en dedikeret kilde $ s $, er målet at opretholde afstanden fra $ s $ til hvert enhver anden knude.

Disse problemer har for nylig fået ekstraordinær opmærksomhed på grund af deres rolle som delproblemer i forskellige mere komplekse og notorisk hårde grafproblemer, især til beregning af flows, bipartite matchings og cuts.

Vores teknikker fører til de første næsten-optimale datastrukturer til disse problemer i forskellige scenarier. For $n$, den antal af knuder i grafen og $m$, den maximale antal kanter i enhver version af grafen, vi præsenterer

* den første randomiserede datastruktur, der opretholder SSR og SCC'er i næsten optimal total opdateringstid $ \tilde {O}(m) $ i en graf, der gennemgår kantsletninger.

* den første randomiserede datastruktur, der opretholder SSSP i delvist dynamiske grafer i den samlede opdateringstid $  \tilde{O}(n^2) $, hvilket er næsten optimalt i tætte grafer.

* de første deterministiske datastrukturer for SSR og SCC for grafer, der gennemgår kantsletninger, og for SSSP i delvist dynamiske grafer, der forbedrer den samlede opdateringstid $ O(mn)$ af Even og Shiloach fra 1981.

§ ACKNOWLEDGMENTS

I would like to start my acknowledgment section with the person that clearly  had the most influence on me throughout my Ph.D. and who made it all possible in the first place: my principal advisor Christian Wulff-Nilsen.

It was first through him that I got to know research in Theoretical Computer Science, and it was him who led me through my first projects as a master student which even culminated in a Best Student Paper at ESA 2018 <cit.>.

From the beginning of my Ph.D., Christian has always encouraged me to work on hard problems, but never left me alone with them even in the face of my many initial misconceptions and mistakes. During the first year, we often worked together in long sessions and nothing impresses me more - still nowadays - than Christian's incredible determination to solve problems even after severe setbacks. And indeed, after some initial setbacks, we developed alone in the first year new algorithms for worst-case update time all-pairs shortest paths <cit.>, decremental SSSP in directed graphs <cit.> and deterministic decremental SSSP in undirected graphs <cit.>. All of which, were accepted to SODA 2020.

At the end of the first year, Christian introduced me to Aaron Bernstein who visited Christian for a week at the time. I had previously tried to improve an algorithm for decremental SSR and SCC, without much luck, but we decided to work on it and try some new approaches. From there, it only took us a few days to get through and solve the problem and we spend the last days going pedantically (but with great enthusiasm) through every proof while eating as much Sushi as Christian's Funding would cover. The paper appeared later in STOC 2019 <cit.> and even got an invitation to the SICOMP special issue.

In January 2019, I took to Boston, where I was more than fortunate to be hosted by Virginia Vassilevska Williams at MIT, much due to the help of my advisor Mikkel Thorup who initiated the contact and to STIBOFONDEN who financed the trip. The months I spent at MIT were among the most interesting of my entire Ph.D.; I met a whole range of open and interesting people to discuss research with, to cycle around Boston, play soccer or to go out for some dinner on Cambridge Street (special thanks to Anders Aamand, Yuval Dagan and Siddhartha Jayanti for making this time so pleasant, but also to all the others I met there!). I also met Nicole Wein, and we worked hard that spring together with Virginia to get some exciting new results for the incremental SSSP problem (and even harder that summer to write up the result). The resulting paper <cit.> was later published at STOC 2020.

Before leaving the U.S., I invited myself to be hosted by Aaron (and for the record, I am his first ever visitor!), who not only agreed to be visited for almost two weeks but also got Thatchaphol Saranurak to join us. It is hard to overestimate how many great papers were started during this time. When we left, we had discussed the algorithmic ideas for an exciting new cut sparsifier, an algorithm to compute a directed expander decomposition and a nice proof sketch for the first adaptive decremental SSR, SCC and SSSP data structures that improve upon the classic ES-tree.

It took only a few weeks after coming back to Copenhagen to find various holes in our arguments, and in the end, we spend almost the entire next year on overcoming shortcomings in our ideas, reinventing components that did not work and pushing even further. The paper <cit.> accepted to FOCS 2020 was one of the results of this hard (but incredibly fun) work, as well, as the paper <cit.> which is currently under submission after merging our cut sparsifier with a technique developed by Jan van den Brand, Danupon Nanongkai, Aaron Sidford and He Sun.

Further, upon returning to Copenhagen, Aaron, Christian and I decided to work on the decremental SSSP algorithm for directed graphs presented at SODA 2020 and throughout the next months, we developed a new perspective on the previous algorithm and finally were able to push through all the way to obtain a near-optimal algorithm for the problem in dense graphs. The resulting paper was accepted recently to FOCS 2020 <cit.>.

This concludes a sketch of the history behind the papers that were published during the Ph.D. project. I am very grateful to have met all the great people that have helped to achieve these exciting results, make this an amazing experience and who have taught me a lot along the way. Much in the same way I want to acknowledge all the great people that are co-authors on manuscripts and who I have worked together with over the years: Thiago Bergamaschi, Debarati Das, Thomas Dueholm Hansen, Jacob Evald, Viktor Fredslund-Hansen, Siddhartha Jayanti, Monika Henzinger, Nikos Parotsidis, Slobodan Mitrović.

I also want to thank Mikkel Thorup who is one of the people who really inspired me in a way that made me want to go for this Ph.D. in the first place and for his general support throughout these years. I am much indebted to Uri Zwick, Virginia and Christian for writing me reference letters that helped to land a Post Doc position at ETH Zurich with Rasmus Kyng. I would further like to thank Uri and Valerie King and Jakob Nordström, for being on the Thesis Committee. I want to thank the people at BARC for creating an environment for high quality research that has helped to meet a lot of really interesting people. I also want to thank both Danupon Nanongkai and Fabian Kuhn for inviting me to give presentations in Stockholm and Freiburg, who were both beyond hospitable.

Finally, I would like to thank all the people who helped me to start the next chapter of my career, in particular, I would like to thank Rasmus Kyng, Sushant Sachdeva, Nikos Parotsidis, Vincent Cohen-Addad and Sebastian Forster.

CHAPTER: INTRODUCTION

§ PROBLEM STATEMENT

In this thesis, we are concerned with three algorithmic graph problems where a weighted directed graph $G=(V,E,w)$ is inputted and a property of the graph is computed and returned by an algorithm.

Single-Source Reachability: In the Single-Source Reachability (SSR) problem, additionally to the weighted digraph $G=(V,E,w)$, a dedicated source vertex $r \in V$ is inputted, and the goal is to compute the set of reachable vertices $R$ such that for every vertex $v \in R$, $r$ can reach vertex $v$, i.e. there exists a path from $r$ to $v$ in $G$, and for every vertex $v \not\in R$, $r$ cannot reach $v$.

Strongly-Connected Components: In the Strongly-Connected Components (SCC) problem, the goal is to output a partition of the vertex set $V$ into sets $X_1, X_2, \dots, X_k$ for some $k$ such that for every pair of vertices $u \in X_i$ and $v \in X_j$, if $i=j$, then $u$ can reach $v$ and vice versa, in which case we say that $u$ and $v$ are strongly-connected, and if $i \neq j$, $u, v$ are not strongly-connected.

Single-Source Shortest Paths:  In the Single-Source Shortest Paths (SSSP) problem, an additional vertex $r \in V$, is inputted and the goal is to return the distance $\dist_G(r,v)$ from $r$ to $v$ , for each $v \in V$.

These problems are among the most fundamental problems in Computer Science due to their various applications in navigation and networks and their role as subroutines in more complex graph algorithmic problems like Maximum Flow and Bipartite Matching <cit.>. Therefore, they are typically covered in undergraduate courses <cit.> and are subject to intensive research in theory and practice. Letting $n = |V|$ and $m = |E|$, the SSSP problem was solved already in 1959 by Dijkstra's algorithm <cit.> which only requires running time $O(m \log n)$. For SSR and SCC even faster algorithms are known due to Tarjan <cit.> since 1972 that achieve running time $O(m)$.

In this thesis, we are interested in the generalization of these graph algorithmic problems to consider a graph $G=(V,E,w)$ that is subject to edge insertions/ deletions and thus there are different versions of $G$ where two consecutive versions only differ in a single edge. Such a graph $G$ is called a dynamic graph in contrast to a static graph $G$ that does not undergo changes. The corresponding dynamic problem versions transform the static algorithmic problems into data structure problems. We define the data structure problems as follows.

Dynamic SSR, SCC and SSSP. In the dynamic SSR problem, the goal is to maintain a data structure $\mathcal{E}_r$ that supports the operations:

* $\textsc{Preprocess}(G, r)$: The data structure is initialized by inputting an initial weighted digraph $G$, and a source vertex $r \in V$.

* $\textsc{Insert}(u,v)$: The data structure processes that the edge $(u,v)$ is inserted into $G$.

* $\textsc{Delete}(u,v)$: The data structure processes that the edge $(u,v)$ is deleted from $G$.

* $\textsc{Query}(v)$: The data structure returns whether $r$ can reach $v$ in the current version of $G$.

In the dynamic SCC problem, a similar data structure is maintained with the difference that an initial source vertex $r$ does not have to be inputted and the query operation takes two vertices $u,v \in V$ as input and returns whether $u,v$ are strongly-connected or not.

In the dynamic SSSP problem, a similar data structure is maintained with the key difference that on query, it returns the distance from $r$ to $v$ instead of outputting whether $r$ reaches $v$.

We point out that two trivial implementations for each kind of dynamic problem exist: we can rerun the static algorithm on the current version of graph $G$ after every update, which leads to high update times but constant query times if implemented carefully. The other extreme is to use a lazy approach where updates are not processed at all but only stored and upon a query operation, the static algorithm is invoked on the current version of $G$. This leads to constant update times but high query times. The goal of the area of dynamic graph algorithms is to improve this trivial trade-off by reusing the information computed for a graph $G$ to compute fundamental graph properties in $G$ after the insertion/ deletion in small time.

In this thesis, we restrict our attention to the setting where the dynamic graph $G$ only undergoes insertions, in which case we say that $G$ is incremental, or exclusively undergoes edge deletions, in which case we say that $G$ is decremental. If $G$ is either incremental or decremental, we also say that $G$ is partially dynamic which is in contrast to the fully dynamic setting where a mix of insertions and deletions is allowed. We also use these graph descriptors to further specify the data structure problem that we are concerned with, for example, the incremental SSSP problem, refers to the data structure problem of dynamic SSSP where the operation $\textsc{Delete}(u,v)$ does not have to be implemented since $G$ is guaranteed to be incremental. We also point out that we often say that there is an algorithm for the incremental SSSP problem, which refers to the algorithm that maintains the underlying data structure.

Adversary Model. We distinguish between two adversary models: we say that the adversary is non-adaptive if the sequence of updates to a graph $G$ is already determined by the adversary before the data structure is initialized (however, this update sequence is still only revealed one-by-one). In contrast, we say the adversary is adaptive if it creates the update sequence on-the-go, i.e. determines the $(i+1)^{th}$ update to $G$ only after the data structure has processed update $i$. We point out that a data structure that is deterministic, i.e. does not make any use of randomization, works in the model of an adaptive adversary. Informally, we say that a data structure is non-adaptive/adaptive if it works in the non-adaptive/adaptive adversary model, and we also sometimes say it works against a non-adaptive/adaptive adversary.

§ MOTIVATION

Partially dynamic SSR and SCC are of great interest for their direct applications especially for detecting cycles or unreachable vertices in dynamic dependency graphs. The incremental SCC problem is further a generalization of the famous incremental Cycle Detection problem which has practical applications in pointer analysis and circuit evaluation (see <cit.> for a discussion of these applications). The decremental SCC problem has further applications to compute Streett Objectives in Graphs and Markov Decision Processes <cit.>, and computing Weak Bisimilarity on Markov Chains <cit.>.

The partially dynamic SSSP has wide-ranging applications:

* Partially dynamic SSSP data structures are often used as internal data structures to solve fully dynamic SSSP and fully dynamic All-Pairs Shortest Paths (APSP), see for example <cit.>, which in turn can be used to maintain properties of real-world graphs undergoing changes.

* Partially dynamic SSSP is often employed as internal data structure for more complex dynamic algorithmic problems such as maintaining the diameter in partially dynamic graphs <cit.> or matchings in incremental bipartite graphs <cit.>.

* Many static algorithms use partially dynamic SSSP algorithms as a subroutine. In particular, a recent line of research shows that many flow problems can be efficiently reduced to decremental SSSP, and recent progress has already led to faster algorithms for multi-commodity flow <cit.>, vertex-capacitated flow, and sparsest vertex-cut <cit.> and min-cost flow problems <cit.>. These reductions are based on algorithms by Garg and Könemann <cit.> and <cit.> who refined the multiplicative update framework to flow problems and use their duals, shortest path problems, to make progress.

Further, we also point out that the theory for Dynamic SSR, SCC and SSSP problems has led to a plethora of new theoretical concepts and general methods. For example, the quest for deterministic Decremental SSR, SCC and SSSP data structures has recently driven theory  to develop a useful notion of directed expanders <cit.> and for generalizing many of the tools from the undirected setting where expander decompositions (see <cit.>) has recently fuelled many exciting new algorithms for a broad variety of problems <cit.>.

Another example is the development of fast and robust dynamic sparsifiers <cit.> which were developed to remedy problems in the theory of Decremental SSSP algorithms for undirected graphs and have since been used in the recent breakthrough result <cit.> for static bipartite matchings, negative-weight shortest paths and the transshipment problem.

We note that in order to be used in applications in a black-box fashion, a data structure has to work in the adaptive adversary model. While a data structure that only works in the non-adaptive adversary model might still be of use to applications, all of the above applications use adaptive data structures even though non-adaptive data structures often have significantly faster update times.

§ PREVIOUS WORK

In our review of previous work, we focus on the dynamic versions of the problems in general directed graphs. For readers interested in the static settings, we refer the reader to the excellent article by Tarjan <cit.> and two recent surveys on SSSP <cit.>. We further point out that in adherence to convention in the field, we state results for partially dynamic algorithms as the cumulative running time over the total update sequence (excluding queries) and point out that all data structures of interest ensure constant query time. We let $n$ denotes the number of vertices, $m$ denote the maximum number of edges in any version of the graph (and we will assume that $m \geq n$), and $W$ be the weight ratio of the graph, that is, the ratio of largest edge weight by smallest edge weight and which for simplicity we assume to be bound by $n^c$ for some large constant $c > 0$ for the rest of this section. We also use $\tilde{O}$-notation and $\Omegatil(\cdot)$ to hide logarithmic factors. Similarly, we use $\Ohat(\cdot)$ and $\Omegahat(\cdot)$ to hide $n^{o(1)}$ factors.

Fully Dynamic SSR, SCC and SSSP. While the fully dynamic setting, that allows for a mix of edge insertions and deletions is clearly a much more general setting than the restricted partially dynamic setting, a series of extremely strong conditional lower bounds for this model renders polynomial improvements over the trivial update/ query trade-off achieved by recomputing from scratch after every update or during every query as unlikely <cit.>.

The ES-tree for partially dynamic SSR and SSSP. The first improvement over the trivial total update time of $\tilde{O}(m^2)$ for partially dynamic SSR and SSSP was given by Even and Shiloach <cit.> in 1981 which has total update time $O(mnW)$ and thereby improves over the trivial approach for dense graphs of small weight ratio. The key idea behind the data structure is a simple trick that allows to maintain, from a fixed root vertex $r$, a BFS tree of depth $\delta$ with total update time $O(m\delta)$ where the above running time follows since $\delta \leq nW$. Therefore the data structure is often referred to as the ES-tree. We point out that originally, the data structure by Even and Shiloach was devised to work only for undirected, unweighted graphs, however, Henzinger and King <cit.> later realized that small modifications suffice to extend the data structure to maintain a directed BFS out-tree from a fixed source $r$ in a directed graphs and thereby made clear that it can be used to certify reachability and to maintain shortest paths. Ever since, the ES-tree has been one of the most widely used and adapted data structures in dynamic graph algorithms and we therefore give a full introduction to the algorithm in <Ref>.

Incremental SSR and SCC. For incremental SSR, it is rather straight-forward to improve the total update time to $\tilde{O}(m)$ total update time by using a dynamic tree data structure (see for example <cit.>).

For the incremental SCC problem, two classic results exists, the first by Haeupler et al. <cit.> gives total update time $\tilde{O}(\min\{mn^{2/3}, m^{3/2}\})$ while the second approach by Bender et al. <cit.> achieves total update time $\tilde{O}(n^2)$. While this still marks the state-of-the-art, we point out that various new approaches <cit.> exist for the incremental cycle detection problem where rather than maintaining the SCCs in the incremental graph $G$, the data structure only has to report when the first non-trivial SCC forms. However, even for this simpler problem, the current state-of-the-art data structures cannot match the near optimal running time bound for incremental SSR.

Decremental SSR and SCC. The first non-trivial data structure for Decremental SSR was the ES-tree with total update time $O(mn)$. Roditty and Zwick further observed in <cit.> that placing a Decremental SSR data structure at a root $r$ and run it on $G$ and the reverse graph $G^{(rev)}$, the data allowed to maintain the set of all vertices that are strongly-connected to $r$. Further, by using a clever random root trick, they derived a reduction from Decremental SCC to Decremental SSR at the additional cost in total update time of only $O(\log n)$, thus, obtaining total update time $\tilde{O}(mn)$ for the SCC problem. In <cit.>, Łącki gave a different approach that decomposed the problem of Decremental SCC into up to $n$ subproblems of Decremental SSR on directed acyclic graphs (DAGs) which can be solved in total time $O(m)$ <cit.>. This constituted the first deterministic algorithm for Decremental SCC with total update time $O(mn)$. This data structure was later further extended by Georgiadis et al. <cit.> to handle more advanced query operations.

The total running time of $O(mn)$, often seen as a fundamental barrier for partially dynamic SSR, SCC and SSSP problems, was finally broken by Henzinger et al. <cit.> to $mn^{0.9+o(1)}$. The authors developed a new algorithm for the Decremental SSR based on clever hitting set techniques. Briefly after, Chechik et al. <cit.> showed that a clever combination of the algorithms in <cit.> and <cit.> can be used to improve the total update time to $\tilde{O}(m \sqrt{n})$.

Partially Dynamic SSSP. While improvements on the upper bounds given by the ES-tree was made for all the partially dynamic SSR and SCC problems, Roditty and Zwick showed in <cit.> that on undirected, weighted graphs, $\tilde{\Omega}(mn)$ total running time is required, or otherwise substantial progress on the static APSP problem was possible. This lower bound was latter strengthened by Abboud and Vassilevska Williams in <cit.> and extended to hold even using algebraic techniques although with a weaker lower bound as proven by Henzinger et al. <cit.>.

Since handling graphs with large weights is highly desirable for applications, research focused subsequently on the relaxed problem of only reporting distance to an $(1+\epsilon)$-approximation. A simple rounding trick (probably first stated in <cit.>) can be used to transform the ES-tree into a data structure that achieves total running time $\tilde{O}(mn)$ for $(1+\epsilon)$-approximate SSSP. While Henzinger et al. <cit.> showed that their approach could be extended to give $(1+\epsilon)$-approximate SSSP in partially dynamic graphs[While the data structure is only shown to work for decremental graphs, we believe that it can be adapted to the incremental setting.] in total update time $mn^{0.9+o(1)}$, this result remained state-of-the-art until this thesis.

§ RELATED WORK

We also give a brief overview of related work. While we state only the best update bounds, we give citations of the current state-of-the art articles in various settings (for example, we sometimes cite the best result for the deterministic setting but only mention the bound achieved in the randomized setting for brevity).

Planar Directed Graphs. For planar graphs, decremental algorithms are known to solve Single-Source Reachability deterministically in near-linear update time <cit.> and SSSP in directed graphs in total update time $\tilde{O}(n^{4/3})$ as shown by <cit.>. The incremental versions of these problems have not received attention yet. The fully-dynamic SSSP problem was recently considered by Charalampopoulos and Karczmarz <cit.> who achieve worst-case update time $\tilde{O}(n^{4/5})$.

Directed Dynamic All-Pairs Shortest Paths. Decremental APSP was first considered by Baswana et al. <cit.> where a data structure with $\tilde{O}(n^3)$ total update time is presented. The authors further present an algorithm for  $(1+\epsilon)$-approximate APSP which was subsequently improved to near-optimal total update time $\tilde{O}(mn)$ by Bernstein <cit.>. The techniques by Bernstein were further recently adapted to the incremental setting in <cit.>, however, only achieving total update time $\tilde{O}(mn^{4/3})$. In the fully dynamic setting, the state-of-the art data structure achieves amortized update time $\tilde{O}(n^2)$ <cit.> and the best worst-case update bound is currently $\tilde{O}(n^{2+2/3})$ <cit.>. Again, allowing for a $(1+\epsilon)$-approximation in the distance estimates, a recent data structure <cit.> achieves worst-case update time $\tilde{O}(n^{2.045})$ ($\tilde{O}(n
^2)$ for undirected graphs). We also note that a substantial amount of research was dedicated to obtaining good dynamic APSP algorithms for planar digraphs where Fakcharoenphol and Rao <cit.> obtained an algorithm with update and query time $\tilde{O}(n^{2/3})$. Subsequently, Abboud and Dahlgaard <cit.> obtained a conditional lower bound of $\tilde{\Omega}(\sqrt{n})$, however, this gap remains unresolved even after considerable effort <cit.>. Finally, there also exists a wide literature on the topic of sensitivity oracles <cit.> where a data structure is computed (often with large preprocessing time) to allow for few updates that can be processed very efficiently and then allows to answer all-pairs shortest paths queries.

Undirected Graphs. In undirected graphs, the problem of connectivity, i.e. whether there exists an undirected path between two query vertices $u$ and $v$, is the pendant to the SSR and SCC problems. Fully dynamic connectivity is a well-studied problem where the fastest data structures take polylogarithmic (worst-case) update time <cit.>. For partially dynamic $(1+\epsilon)$-approximate SSSP, a breakthrough result by Henzinger et al. <cit.> achieves total update time $m^{1+o(1)}$ and a recent goal in this setting has become to obtain deterministic or at least adaptive algorithms <cit.>. There further exist a plethora of work on the dynamic decremental APSP problem with varying approximation guarantees <cit.> and in the fully dynamic setting <cit.> and we also point out that algebraic techniques were developed for both fully dynamic SSSP and APSP <cit.>.

§ CONTRIBUTION

In this thesis we present significant progress on the partially dynamic SSR, SCC and SSSP problems. In fact, we present the first data structures for all three problems that are near-optimal (although the data structures for SSSP are only near-optimal in very dense graphs).

A Near-Linear Update Time Randomized Algorithm for Decremental SSR and SCCs. Our first contribution is an efficient randomized near-linear update time data structure for decremental SSR and SCC. This update time should be compared to the currently best total update time of $\tilde{O}(m\sqrt{n})$ <cit.>.

theoremsccMain[see <cit.>]

Given a decremental, directed graph $G=(V,E)$ and a dedicated source vertex $r \in V$, then we can maintain explicitly

* the strongly-connected components of $G$, and

* the set $R$ of vertices that are reachable from $r$.

The data structure runs in total expected update time $\tilde{O}(m)$ and works against an adaptive adversary, however, if path-queries are allowed it only works against a non-adaptive adversary.

Near-Optimal Partially Dynamic SSSP in Dense Digraphs. Further, we present the first near-optimal data structure for partially dynamic SSSP in weighted directed graphs. This bound should be compared to the data structure by Henzinger et al. <cit.>.

Given a partially dynamic input graph $G=(V,E,w)$, a dedicated source $r \in V$ and $\epsilon > 0$, there is a randomized algorithm that maintains a distance estimate $\widetilde{\mathbf{dist}}(r,x)$, for every $x \in V$, such that

\[
{\mathbf{dist}}_G(r,x) \leq \widetilde{\mathbf{dist}}(r,x) \leq (1+\epsilon) {\mathbf{dist}}_G(r,x)
\]

at any stage w.h.p. The algorithm has total expected update time $\tilde{O}(n^2 \log W/\poly(\epsilon))$. Distance queries are answered in $O(1)$ time, and a corresponding path $P$ can be returned in $O(|P|)$ time. For the decremental version the data structure is non-adaptive, however, for the incremental version of the problem, our data structure is even deterministic.

We point out that in <cit.>, a data structure for the decremental SSSP problem is given with total update time $\tilde{O}(mn^{2/3}\log W/\poly(\epsilon))$ which constitutes the best result on sparse digraphs. However, we only present the result on dense graphs in this thesis.

Deterministic Algorithms for Decremental SSR, SCC and SSSP. Finally, we present the first deterministic data structures for partially dynamic SSR, SCC and SSSP that improve upon the total update time of Even and Shiloach's data structure from 1981. In fact, this even is the first adaptive data structure that improves on the $O(mn)$ total running time achieved in <cit.> when we want to support path-queries which are often crucial for applications.

theoremContributionDetSCCResult[see <cit.>]

Given a decremental, directed graph $G=(V,E)$, we can deterministically maintain the strongly-connected components of $G$ in total update time $mn^{2/3+o(1)}$. Further the data structure allows for constant time queries which upon inputting two vertices $u,v \in V$, outputs whether they are strongly-connected or not.

The data structure can also, given a dedicated source vertex $r \in V$, maintain within the same update time the set of vertices reachable from $r$ and offers a constant time query which upon inputting a vertex $v \in V$, returns whether $r$ reaches $v$.

theoremContributionDetSSSPResult[see <cit.>]

Given a decremental dynamic input graph $G=(V,E,w)$, a dedicated source $r \in V$ and $\epsilon > 0$, there is a deterministic algorithm that maintains a distance estimate $\widetilde{\mathbf{dist}}(r,x)$, for every $x \in V$, such that

\[
{\mathbf{dist}}_G(r,x) \leq \widetilde{\mathbf{dist}}(r,x) \leq (1+\epsilon) {\mathbf{dist}}_G(r,x)
\]

at any stage of the graph. The algorithm has total update time $n^{2+2/3+o(1)} \log W/\poly(\epsilon)$. Distance queries are answered in $O(1)$ time, and a corresponding path $P$ can be returned in $|P|n^{o(1)}$ time.

Both results for decremental SSSP (i.e. the results from <cit.> and <cit.>) build heavily upon the article <cit.> which was part of the Ph.D. project but is not featured in this thesis since its results were superseded by the results presented in this thesis. Further, we point out that <Ref> and <Ref> indeed apply to partially dynamic graphs (instead of only decremental graphs) when considering the results from <cit.> and <Ref>.

§ CONTRIBUTION BEYOND THE THESIS

While the thesis focuses on the problems of partially dynamic SSR, SCC and SSSP in directed graphs, various results obtained during the Ph.D. project, have contributed to the current state of the art on dynamic graph algorithms. For completeness, we list here the contributions that are not covered by this thesis:

* The article <cit.> presents the first fully dynamic APSP algorithm with deterministic worst-case update time beyond the $\tilde{O}(n^{2+3/4})$ time bound given in 2015 by Thorup <cit.>. The article further gives a randomized data structure that is more general than the current state-of-the-art data structure with best randomized worst-case update time $\tilde{O}(n^{2+2/3})$. Finally, it answers the question for a non-trivial dynamic APSP data structure with subcubic space as the latter algorithm only requires $\tilde{O}(n^2)$ space.

* The article <cit.> presents an improvement for the decremental SSSP problem on undirected graphs. The achieved total update time of $mn^{0.5+o(1)}$ should be compared to the results by Chechik and Bernstein <cit.> that achieve running time $\tilde{O}(\min\{mn^{3/4}, n^2\})$. Thus, the new data structure improves over the state-of-the-art whenever the graph $G$ is sufficiently sparse.

* The article <cit.> presents the first non-trivial algorithm to maintain graph sparsifiers against an adaptive adversary. In particular, on a fully dynamic graph, the data structure can maintain a $O(\polylog n)$-approximate spanner, cut-sparsifier or spectral-sparsifier with polylogarithmic update time.

* The article <cit.> investigates a generalization of the classic Thorup-Zwick Distance Oracles <cit.> where a static data structure is computed on a graph where each vertex is given a color (possibly many vertices receive the same color) and then has to answer queries given a vertex $v$ and a color $c$ for the (approximately) nearest $c$-colored vertex from $v$. The article demonstrates that the latter problem is strictly harder by establishing hardness in the cell-probe model, and gives an oracle with query times that are optimal up to a constant factor based on previous techniques from <cit.>.

* The article <cit.> of which excerpts are used in this thesis to derive <Ref>, also presents new conditional lower bounds for the exact weighted partially dynamic SSSP. The strongest among these lower bounds states that even in undirected graphs, for any sparsity $m$, there cannot be an exact algorithm, with preprocessing time $m^{2-\delta}$ and update and query time $m^{1-\delta}$ for any arbitrarily small constant $\delta > 0$, unless the $k$-Cycle Hypothesis is falsified. This lower bound also applies to algebraic algorithms which was previously not possible since lower bound reductions were based on the "combinatorial" static APSP conjecture.

* The article <cit.> from which we present the proof of <Ref> and <Ref>, presents a new framework for directed expanders and a new technique called congestion balancing. While we touch on these new developments partially in this thesis, we do not cover them in detail. We also do not cover a simple algorithm that is derived in <Ref> by using the technique of congestion balancing in conjunction with a recent result by Wajc <cit.> and which gives the first $\tilde{O}(m)$ total update time algorithm for decremental $(1-\epsilon)$-approximate bipartite matchings.

§ ORGANISATION

The rest of the thesis is concerned with presenting data structures as described in <Ref>. We also give full proofs for all stated theorems, however, we will omit or only sketch several intermediate results.

Let us now provide an overview of the thesis, chapter by chapter:

<Ref>. In this chapter, basic notation and preliminaries for the rest of the thesis are introduced where we try to adhere to conventions from the field of dynamic graph algorithms. Further, we give a brief introduction to the data structure by Even and Shiloach <cit.> (the so called ES-tree) in <Ref> which we recommend to readers not overly familiar with the data structure since many of the presented techniques rely on modifications and new insights to the classic ES-tree.

We further give a short reduction in <Ref> which allows us to assume that the weight ratio of partially dynamic graphs $G$ is bound over all stages by a small polynomial in $n$, at the expense of introducing a $\log nW$ factor in the running time. While the proof is neither insightful nor novel, we state it here and use it implicitly in the rest of the thesis.

<Ref>. We then present a randomized data structure for the decremental SCC problem with expected near-linear update time $\tilde{O}(m)$. This data structure is straight-forwardly extended to also maintain SSR in decremental graphs. This gives the result stated in <Ref>. The chapter is based on the STOC'2019 publication <cit.>.

<Ref>. Building upon some of the techniques introduced in <Ref>, we then present a randomized data structure for the decremental SSSP problems with expected update time $\tilde{O}(n^2)$. We point out however that the chapter is entirely self-contained and does not require the reader to have read <Ref>, however, it does omit some proofs which are repetitive.
This chapter is based on the SODA'2020 publication <cit.> and the FOCS'2020 publication <cit.> which supersedes the results obtained in the former publication (the chapter introduces both approaches and highlights the improvements in the framework obtained in <cit.>).

<Ref>. We present the first deterministic data structures that supersede the result by Even and Shiloach for decremental SSR, SCC and SSSP. We point out that these results require a new range of techniques for directed expanders. Since this thesis is focused on partially dynamic SSR, SCC and SSSP data structures, we do not cover proofs for these techniques, but rather give an intuitive approach to expanders and illustrate how to obtain the data structures described in <Ref> and <Ref> from directed expander techniques. We then give a thorough proof of <Ref> which is based on the techniques from <Ref> and <cit.>. The chapter is however self-contained as we give a brief (re)-introduction to the framework from <Ref>.

<Ref>. In this chapter, we present a deterministic incremental SSSP data structure with total update time $\tilde{O}(n^2)$. The data structure is inspired by a data structure for undirected graphs <cit.> however it requires many additional insights to make the same approach work in directed graphs. The chapter is based on the STOC'2020 publication <cit.>.

<Ref>. Finally, we give a conclusion where we reflect on the contributions of this thesis and list a range of related open problems motivated by this work.

CHAPTER: PRELIMINARIES

§ NOTATION AND BASIC DEFINITIONS

We let a graph $H$ refer to a weighted, directed graph with vertex set denoted by $V(H)$ of size $n_H$, edge set $E(H)$ of size $m_H$ and weight function $w_H : E(H) \rightarrow [1,W] \cup \{\infty\}$. We say that $H$ is a decremental graph if it is undergoing a sequence of edge deletions and edge weight increases (also referred to as updates), and refer to version $t$ of $H$, or $H$ at stage $t$ as the graph $H$ obtained after the first $t$ updates have been applied. In this article, we denote the (decremental) input graph by $G=(V,E,w)$ with $n = |V|$ and $m = |E|$ (where $m$ refers to the number of edges of $G$ at stage $0$). In all subsequent definitions, we often use a subscript to indicate which graph we refer to, however, when we refer to $G$, we often omit the subscript.

Neighborhoods and Degree.  We let $\mathcal{N}^{in}_H(v) = \{ u \;|\; (u,v) \in E(H) \}$ and $\mathcal{N}^{out}_H(v)  = \{ u \;|\; v \in \mathcal{N}^{in}_H(u)\}$ denote the in-neighborhood and out-neighborhoods of $v \in V$. We let the neighborhood $\mathcal{N}_H(v)$ of $v$ be defined by $\mathcal{N}_H(v) = \mathcal{N}^{in}_H(v) \cup \mathcal{N}^{out}_H(v)$. The weighted in-degree and out-degree
of a vertex $u$ are $\deg^{in}(u)=w(E(V,u))$ and $\deg^{out}(u)=w(E(u,V))$,
respectively. The weighted degree of $u$ is $\deg(u)=\deg^{in}(u)+\deg^{out}(u)$.
The volume of a set $S$ is $\vol(S)=\sum_{u\in S}\deg(u)$.

Subgraphs, Cuts and Vertex Subsets. We let $H[X]$ refer to the subgraph of $H$ induced by $X$, i.e. $H[X] = (X, E_H(X,X), w_H)$. We use $H \subseteq G$ to denote that $V(H) = V(G)$ and $E(H) \subseteq E(G)$. For graph $H$, and any two disjoint subsets $X,Y \subseteq V(H)$, we let $E_H(X)$ be the set of edges in $E(H)$ with an endpoint in $X$, and $E_H(X,Y)$ denote the set of edges in $E(H)$ with tail in $X$ and head in $Y$. We say that for $S \subseteq V$, $(S, V \setminus S)$ is a vertex cut (sometimes simply cut) and sometimes denote $V \setminus S$ by $\overline{S}$. For any $S$, let $\delta^{out}(S)=w(E(S,V\setminus S))$ and $\delta^{in}(S)=w(E(V\setminus S,S))$ denote the total weight of edges going out and coming in to $S$, respectively.

Balanced Cuts. We say that cut $(S,V\setminus S)$ is $\epsilon$-balanced if $\vol(S)\ge\epsilon\vol(V)$, and it
is $\phi$-sparse if $\min\{\delta^{in}(S),\delta^{out}(S)\}<\phi\vol(S)$.
We say that $(L,S,R)$ is a vertex-cut of $G$ if $L$,$S$, and $R$ partition the vertex set $V$,
and either $E(L,R)=\emptyset$ or $E(R,L)=\emptyset$.

Assuming that $|L|\le|R|$,
$(L,S,R)$ is $\epsilon$-vertex-balanced if $|L|\ge\epsilon|V|$,
and it is $\phi$-vertex-sparse if $|S|<\phi|L|$.

Contractions. We define the graph $H / X$ to be the graph obtained from $H$ by contracting all vertices in $X$ into a single node (we use the word node instead of vertex if it was obtained by contractions). Similarly, for a set of pairwise disjoint vertex sets $X_1, X_2, \dots, X_k$, we let $H / \{X_1, X_2, \dots, X_k\}$ denote the graph $((((H / X_1) / X_2) \dots ) / X_k)$. If $\mathcal{V}$ forms a partition of $V$, we use the convention to denote by $X^v$ the node in $G/ \mathcal{V}$ that contains $v \in V$, i.e. $v \in X^v$. To undo contractions, we define the function $\textsc{Flatten}(X)$ for a family of sets $X$ by $\textsc{Flatten}(X) = \bigcup_{x \in X} x$.

Reachability and Strong-Connectivity. For graph $H$ and any two vertices $u,v \in V(H)$, we let $u \leadsto_H v$ denote that $u$ can reach $v$ in $H$, and $u \rightleftarrows_H v$ that $u$ can reach $v$ and vice versa (in the latter case, we also say $u$ and $v$ are strongly-connected). For any sets $X,Y \subseteq V(H)$, we say that $X \leadsto_H Y$ if there exists some $x \in X$, $y \in Y$ such that $x \leadsto_H y$; we define $X \rightleftarrows_H Y$ analogously. We say that the partition of $V(H)$ induced by the equivalence relation $\rightleftarrows_H$ is the set of strongly-connected components (SCCs). We denote by $\textsc{Condensation}(H)$ the condensation of $H$, that is the graph obtained by contracting each SCC in $H$ into a node.

Distances, Diameter and Balls. We let $\mathbf{dist}_H(u,v)$ denote the distance from vertex $u$ to vertex $v$ in graph $H$ and denote by $\pi_{u,v, H}$ the corresponding shortest path (we assume uniqueness by implicitly referring to the lexicographically shortest path). We define the weak diameter of $X \subseteq V(H)$ in $H$ by $\mathbf{diam}(X, H) = \max_{x,y \in X} \mathbf{dist}_H(x,y)$. We define a ball $B_{out}(r, \delta)$ for some source $r \in V$ and positive real $\delta \in \mathbb{R}_{>0}$ to be the set of vertices at distance at most $\delta$ from $r$, i.e. $B_{out}(r, \delta) = \{ v \in V \; | \; \mathbf{dist}_G(r, v) \leq \delta \}$. We similarly define $B_{in}(r, \delta)$ to be $B_{out}(r, \delta)$ in the graph $G$ where edge directions are reversed.

$S$-Distances. We define the notion of $S$-distances for any $S \subseteq V(H)$ where for any pair of vertices $u,v \in V(H)$, the $S$-distance $\mathbf{dist}_H(u,v, S)$ denotes the minimum number of vertices in $S \setminus \{v\}$ encountered on any path from $u$ to $v$. Alternatively, the $S$-distance corresponds to $\mathbf{dist}_{H'}(u,v)$ where $H'$ is a graph with edges $E_{out}(S)$ of weight $1$ and edges $E \setminus E_{out}(S)$ of weight $0$. It therefore follows that for any $u,v \in V(H)$, $\mathbf{dist}_H(u,v) = \mathbf{dist}_H(u,v,V)$.

Partitions. For two partitions $P$ and $P'$ of a set $U$, we say that partition $P$ is a melding for a partition $P'$ if for every set $X \in P'$, there exists a set $Y \in P$ with $X \subseteq Y$. We also observe that melding is transitive, thus if $P$ is a melding for $P'$ and $P'$ a melding for $P''$ then $P$ is a melding for $P''$.

§ THE ES-TREE

The starting point for all data structures derived in the rest of this thesis is the ES-tree. We first state the formal result obtained by Even and Shiloach <cit.> (in a slightly extended version)

Given a directed, unweighted, partially dynamic graph $G=(V,E)$, a fixed source vertex $r \in V$ and a depth $\delta > 0$, there exists a data structure $\mathcal{E}_r$ called the ES-tree that explicitly maintains for every $v \in B_{out}(r, \delta)$, the distance from $r$ to $v$ in any version of $G$. The algorithm runs in total update time $O(m\delta)$ and has query time $O(1)$. A corresponding shortest $r$-to-$v$ path $P$ can be returned in time $O(|P|)$.

We point out that $B_{out}(r, \delta)$ in the above theorem refers to the ball at $r$ in the current version of the graph $G$, i.e. the set $B_{out}(r, \delta)$ is decremental itself and for any vertex $v$ at distance at most $\delta$ at some stage $i$ of $G$, we can query at stage $i$, the exact distance from $r$ to $v$. We also point out that for vertices not in $B_{out}(r, \delta)$, the data structure can be implemented to return $\infty$ (or any other sentinel). We present the data structure for a decremental graph, however, it is straight-forward to obtain the same result in incremental graphs.

The Algorithm. We maintain distances from a fixed source $r \in V$ to each vertex $v$ in $V$ up to distance $\delta > 0$ by storing a distance estimate $\widetilde{\mathbf{dist}}(r,v)$ that is initialized to the distance between $r$ and $v$ in $G$ along with a shortest-path tree $T$ rooted at $r$. On update $(u,v)$, we delete the edge from $G$ and possibly from $T$. Then, if possible, we extract $w_{min} \in V \setminus \{r\}$, the vertex with smallest distance estimate among vertices without incoming edge in $T$. (For the first extraction, we always have $w_{min} = v$.) For this vertex $w_{min}$, we then try to find a vertex $x \in \mathcal{N}^{in}(w_{min})$ such that adding $(x, w_{min})$ to $T$ implies $\mathbf{dist}_T(r,w_{min}) \leq \widetilde{\mathbf{dist}}(r,w_{min})$. We therefore search in $\mathcal{N}^{in}(w_{min})$ for an $x$ that satisfies
\begin{equation}
\label{eq:enforce}
\widetilde{\mathbf{dist}}(r,x)+ w(x,w_{min}) \leq \widetilde{\mathbf{dist}}(r,w_{min}).
\end{equation}

If no such $x$ exists, then $\widetilde{\mathbf{dist}}(r,w_{min})$ has to be incremented, and we set $T$ to $T \setminus N^{out}(w_{min})$. If $\widetilde{\mathbf{dist}}(r,w_{min}) > \delta$, we set it to $\infty$ and remove $w_{min}$ from the tree. We iterate the process until $T$ is spanning for vertices with distance estimate $< \infty$.

Total Update Time. We claim that for each distance estimate value $\widetilde{\mathbf{dist}}(r,v)$, $\mathcal{N}^{in}(v)$ has to be scanned only once. This follows since if Equation <ref> is satisfied for a neighbor then the edge is taken into the tree $T$ until deleted, but if it does not satisfy the equation, it never has to be considered at the current distance estimate value of $v$ since the left-hand-side of the equation is monotonically increasing over time and thus the equation cannot be satisfied before the right-hand-side is increased. Since estimates increase monotonically, the total update time can be bound by $O(\sum_{v \in V} |\mathcal{N}^{in}(v)| \delta) = O(m \delta)$.

Correctness of the Algorithm. It remains to show that after the algorithm to reconstruct the tree $T$ terminates, we have for all $x \in B_{out}(r, \delta)$, that $\widetilde{\mathbf{dist}}(r, x) = {\mathbf{dist}}(r,x)$.

While a formal argument would require nested induction, we simply observe that a vertex $x$ at distance $d \leq \delta$, always has the vertex $y$ that precedes it on the shortest path from $r$-to-$x$ in its in-neighborhood. An inductive argument over the distances from $r$ thus shows that we can always add an in-edge for $x$ to the tree $T$ that ensures that the distance estimate is at most the real distance. On the other hand, since $T$ is a subset of $G$ after each stage, each path in the tree is at most of weight equal to the shortest path distances.

§ REDUCING THE WEIGHT DEPENDENCY IN PARTIALLY DYNAMIC SSSP

Here, we also give a small reduction that extends $(1+\epsilon)$-approximate partially dynamic SSSP for weight ratio $n^4$, to any weight ratio $W$ at the expense of an additional $\log W$ factor. Throughout this thesis, we are therefore only concerned with obtaining a polylogarithmic dependency on $W$ since by the theorem below, we can then reduce the dependency on $W$ to $\log nW$. We will not state explicitly in the sections that we use the below theorem, however, claim the update times in
<Ref> by making use of it.

For any $1/2 > \epsilon > 1/n$, given a data structure $\mathcal{E}_r$ that maintains $(1 + \epsilon)$-approximate partially dynamic SSSP on a graph $H$ in time $\mathcal{T}_{SSSP}(m_H, n_H, \epsilon, W_H)$ (where we assume that distance estimates are maintained explicitly). Then, there exists a data structure, that maintains  $(1 + 6\epsilon)$-approximate partially dynamic SSSP on a graph $G$ in time

\[
\left( (m+n) \log n / \epsilon + \mathcal{T}_{SSSP}(m, n, \epsilon, n^4)\right) \cdot O(\log(nW) ).
\]

Given the graph $G$ with weight ratio $W$. Assume that the smallest weight is $1$ and the largest weight $W$ (this is without loss of generality). Throughout the update sequence, for $i = 0, 1, \dots, \lceil \lg Wn \rceil + 1$, maintain a graph $G_i$ derived from $G$ by removing all edges of weight larger $2^i$ and by rounding all remaining edges up to the nearest multiple of $2^{i}/ n^2$. Finally, run a data structure $\mathcal{E}^i_r$ on each such graph $G_i$ and maintain for each for each $v \in V$, a min-priority heap over the distance estimates $\widetilde{\mathbf{dist}}^i(r,v)$ in all data structures $\mathcal{E}^i_r$.

We first observe that the resulting graphs $G_i$ clearly have weight ratio $n^2$ by definition. For the running time, we first observe that we have $O(\log nW)$ data structures $\mathcal{E}^i_r$. Further, each of the $m$ updates to $G$ results in at most $O(\log nW)$ updates to graphs $G_i$. The data structures $\mathcal{E}^i_r$ update the distance estimates at most $O(\mathcal{T}_{SSSP}(m, n, \epsilon, n^2))$ times. Updating the heap data structure only when distance estimates change by $(1+\epsilon)$ which occurs at most $O(\log(nW)/\epsilon)$ times for each vertex, and using that each update to the heap is at cost $O(\log \log Wn) = O(\log n)$, we derive our final bound on the running time.

For correctness, observe that during stage $t$, for a vertex $v$ at distance $2^{i-1} < \mathbf{dist}(r,v) \leq 2^i$ for some $i$, in the graph $G_i$, the shortest path from $r$ to $v$ is at most $(1+2/n) \mathbf{dist}(r,v)$ since each edge on the shortest $r$-to-$v$ path in $G$ has weight at most $2^i$ and is thus in $G_i$ and further each edge incurs additive error at most $2^i/n^2$ by the rounding of edges combined with the fact that the distance is at least $2^{i-1}$ and that there are at most $n$ edges on any simple path. Further, the distance in each $G_i$ between any pair of vertices is at least as large as in $G$. The final approximation guarantee stems from the fact that $(1+\epsilon) \cdot (1+2/n) \leq (1+\epsilon) \cdot (1+2\epsilon) \leq (1+6\epsilon)$ since for $0 \leq x \leq 1$, $1+x \leq e^x \leq 1+2x$.

CHAPTER: A RANDOMIZED ALGORITHM FOR DECREMENTAL SSR AND SCCS

In this section, we prove the following result.

We point out that it suffices to maintain the strongly-connected components of $G$ since we can then run the decremental SCC data structure on the graph $G \cup (V \times \{r\}$, that is the graph $G$ with an additional edge from every vertex $v \in V$ to $r$. Observe that a vertex $v$ is reachable from $r$ in $G$ if and only if $r$ and $v$ are strongly-connected in $G \cup (V \times \{r\})$.

We next give an overview on how to obtain the Decremental SCC data structure presented in <Ref>. We then present our one of our key insights, a generalization of the ES-tree, and in the final sections show how to use this insight to obtain a fast data structure.

§ OVERVIEW

We start by introducing the graph hierarchy maintained by our algorithm, followed by a high-level overview of our algorithm.

High-level overview of the Hierarchy.  Our hierarchy has levels $0$ to $\lfloor \lg n \rfloor + 1$ and we associate with each level $i$ a subset $E_i$ of the edges $E$. The sets $E_i$ form a partition of $E$; we define the edges that go into each $E_i$ later in the overview but point out that we maintain $E_{\lfloor \lg n \rfloor + 1} = \emptyset$. We define a graph hierarchy $\hat{G} = \{\hat{G}_0, \hat{G}_1, .. ,\hat{G}_{\lfloor \lg n \rfloor + 1}\}$ such that each graph $\hat{G}_i$ is defined as

\[
\hat{G}_i = \textsc{Condensation}((V, \bigcup_{j < i} E_j)) \;\cup\; E_{i}
\]

That is, each $\hat{G}_i$ is the condensation of a subgraph of $G$ with some additional edges. As mentioned in the preliminary section, we refer to the elements of the set $\hat{V}_i = V(\hat{G}_i)$ as nodes to distinguish them from vertices in $V$. We use capital letters to denote nodes and small letters to denote vertices. We let $X_i^v$ denote the node in $\hat{V}_i$ with $v \in X_i^v$. Observe that each node $X$ corresponds to a subset of vertices in $V$ and that for any $i$, $\hat{V}_i$ can in fact be seen as a partition of $V$. For $\hat{G}_0 = \textsc{Condensation}((V, \emptyset)) \;\cup\; E_{0}$, the set $\hat{V}_0$ is a partition of singletons, i.e. $\hat{V}_0 = \{ \{v\} | v \in V\}$, and $X_0^v = \{ v\}$ for each $v \in V$.

Observe that because the sets $E_i$ form a partition of $E$ and $E_{\lfloor \lg n \rfloor + 1} = \emptyset$, the top graph $\hat{G}_{\lfloor \lg n \rfloor + 1}$ is simply defined as

\begin{align*}
\hat{G}_{\lfloor \lg n \rfloor + 1} &= \textsc{Condensation}((V, \bigcup_{j < \lfloor \lg n \rfloor + 1} E_j)) \;\cup\; E_{\lfloor \lg n \rfloor + 1} \\ &= \textsc{Condensation}((V,E)).
\end{align*}

Therefore, if we can maintain $\hat{G}_{\lfloor \lg n \rfloor + 1} $ efficiently, we can answer queries on whether two vertices $u,v \in V$ are in the same SCC in $G$ by checking if $X_{\lfloor \lg n \rfloor + 1}^u$ is equal to $X_{\lfloor \lg n \rfloor + 1}^v$.

Let us offer some intuition for the hierarchy. The graph $\hat{G}_0$ contains all the vertices of $G$, and all the edges of $E_0 \subseteq E$. By definition of $\textsc{Condensation}(\cdot)$, the nodes of $\hat{G}_1$ precisely correspond to the SCCs of $\hat{G}_0$. $\hat{G}_1$ also includes the edges $E_0$ (though some of them are contracted into self-loops in $\textsc{Condensation}((V, E_0))$), as well as
the additional edges in $E_1$. These additional edges might lead to $\hat{G}_1$ having larger SCCs than those of $\hat{G}_0$; each SCC in $\hat{G}_1$ then corresponds to a node in $\hat{G_2}$. More generally, the nodes of $\hat{G}_{i+1}$ are the SCCs of $\hat{G}_{i}$.

As we move up the hierarchy, we add more and more edges to the graph, so the SCCs get larger and larger. Thus, each set $\hat{V}_i$ is a melding for any $\hat{V}_j$ for $j \leq i$; that is for each node $Y \in \hat{V}_j$ there exists a set $X \in \hat{V}_i$ such that $Y \subseteq X$. We sometimes say we meld nodes $Y, Y' \in \hat{V}_j$ to $X \in \hat{V}_{i}$ if $Y, Y' \subseteq X$ and $j < i$. Additionally, we observe that for any SCC $Y \subseteq \hat{V}_i$ in $\hat{G}_i$, we meld the nodes in SCC $Y$ to a node in $X \in \hat{V}_{i+1}$, and $X$ consists exactly of the vertices contained in the nodes of $Y$. More formally, $X = \textsc{Flatten}(Y)$.

To maintain the SCCs in each graph $\hat{G}_i$, our algorithm employs a bottom-up approach. At level $i+1$ we want to maintain SCCs in the graph with all the edges in $\bigcup_{j \leq i+1} E_j$, but instead of doing so from scratch, we use the SCCs maintained at level $\hat{G}_i$ as a starting point. The SCCs in $\hat{G}_i$ are precisely the SCCs in the graph with edge set $\bigcup_{j \leq i} E_j$; so to maintain the SCCs at level $i+1$, we only need to consider how the sliver of edges in $E_{i+1}$ cause the SCCs in $\hat{G}_{i}$ to be melded into larger SCCs (which then become the nodes of $\hat{G}_{i+2}$).

If the adversary deletes an edge in $E_i$, all the graphs $\hat{G}_{i-1}$ and below remain unchanged, as do the nodes of $\hat{G}_{i}$. But the deletion might split apart an SCC in $G_i$, which will in turn cause a node of $\hat{G}_{i+1}$ to split into multiple nodes. This split might then cause an SCC of $\hat{G}_{i+1}$ to split, which will further propagate up the hierarchy.

In addition to edge deletions caused by the adversary, our algorithm will sometimes move edges from $E_i$ to $E_{i+1}$. Because the algorithm only moves edges up the hierarchy, each graph $\hat{G}_i$ is only losing edges, so the update sequence remains decremental from the perspective of each $\hat{G}_i$. We now give an overview of how our algorithm maintains the hierarchy efficiently.

Maintaining SCCs with ES-trees. Consider again graph $\hat{G}_0$ and let $X \subseteq \hat{V}_0$ be some SCC in $\hat{G}_0$ that we want to maintain. Let some node $X'$ in $X$ be chosen to be the center node of the SCC (In the case of $\hat{G}_0$, the node $X'$ is just a single-vertex set $\{ v \}$). We then maintain an ES in-tree and an ES out-tree from $X'$ that spans the nodes in $X$ in the induced graph $\hat{G}_0[X]$. We must maintain the trees up to distance $\mathbf{diam}(\hat{G}_0[X])$, so the total update time is $O(|E(\hat{G}_0[X])|* \mathbf{diam}(\hat{G}_0[X]))$ (recall <Ref>).

Now, consider an edge deletion to $\hat{G}_0$ such that the ES in-tree or ES out-tree at $X'$ is no longer a spanning tree. Then, we detected that the SCC $X$ has to be split into at least two SCCs $X_1, X_2, .., X_k$ that are node-disjoint with $X = \bigcup_i X_i$. Then in each new SCC $X_i$ we choose a new center and initialize a new ES in-tree and ES out-tree.

Exploiting small diameter. The above scheme clearly is quite efficient if $\mathbf{diam}(\hat{G}_0)$ is very small. Our goal is therefore to choose the edge set $E_0$ in such a way that $\hat{G}_0$ contains only SCCs of small diameter. We therefore turn to some insights from <cit.> and extract information from the ES in-tree and out-tree to maintain small diameter. Their scheme fixes some $\delta > 0$ and if a set of nodes $Y \subseteq X$ for some SCC $X$ is at distance $\Omega(\delta)$ from/to $\textsc{Center}(X)$ due to an edge deletion in $\hat{G}_0$, they find a node separator $S$ of size $O(\min\{|Y|, |X \setminus Y|\}\log n / \delta)$; removing $S$ from  $\hat{G}_0$ causes $Y$ and $X \setminus Y$ to no longer be in the same SCC. We use this technique and remove edges incident to the node separator $S$ from $E_0$ and therefore from $\hat{G}_0$. One subtle observation we want to stress at this point is that each node in the separator set appears also as a single-vertex node in the graph $\hat{G}_1$; this is because each separator node $\{ s\}$ for some $s \in V$ is not melded with any other node in $\hat{V}_0$, as it has no edges in $\hat{G}_0$ to or from any other node.

For some carefully chosen $\delta = \Theta(\log^2 n)$, we can maintain $\hat{G}_0$ such that at most half the nodes in $\hat{V}_0$ become separator nodes at any point of the algorithm.  This follows since each separator set is small in comparison to the smaller side of the cut and since each node in $\hat{V}_0$ can only be $O(\log n)$ times on the smaller side of a cut.

Reusing ES-trees. Let us now refine our approach to maintain the ES in-trees and ES out-trees and introduce a crucial ingredient devised by Roditty and Zwick <cit.>. Instead of picking an arbitrary center node $X'$ from an SCC $X$ with $X' \in X$, we are going to pick a vertex $r \in \textsc{Flatten}(X) \subseteq V$ uniformly at random and run our ES in-tree and out-tree $\mathcal{E}_{r}$ from the node $X_0^r$ on the graph $\hat{G}_0$. For each SCC $X$ we denote the randomly chosen root $r$ by $\textsc{Center}(X)$. In order to improve the running time, we reuse ES-trees when the SCC $X$ is split into SCCs $X_1, X_2, .. , X_k$, where we assume wlog that $r \in \textsc{Flatten}(X_1)$, by removing the nodes in $X_2, .., X_k$ from $\mathcal{E}_{r}$ and setting $\textsc{Center}(X_1) = r$. Thus, we only need to initialize a new ES-tree for the SCC $X_2, .. , X_k$. Using this technique, we can show that each node is expected to participate in $O(\log n)$ ES-trees over the entire course of the algorithm, since we expect that if a SCC $X$ breaks into SCCs $X_1, X_2, .. , X_k$ then we either have that every SCC $X_i$ is of at most half the size of $X$, or with probability at least $1/2$ that $X_1$ is the new SCC that contains at least half the vertices, i.e. that the random root is contained in the largest part of the graph. Since the ES-trees work on induced graphs with disjoint node sets, we can therefore conclude that the total update time for all ES-trees is $O(m \log n* \mathbf{diam}(\hat{G}_0))$.

We point out that using the ES in-trees and out-trees to detect node separators as described above complicates the analysis of the technique by Roditty and Zwick <cit.> but a clever proof presented in <cit.> shows that the technique can still be applied. In our paper, we present a proof that can even deal with some additional complications and that is slightly simpler.

A contrast to the algorithm of Chechik et al <cit.>.

Other than our hierarchy, the overview we have given so far largely comes from the algorithm of Chechik et al <cit.>. However, their algorithm does not use a hierarchy of graphs. Instead, they show that for any graph $G$, one can find (and maintain) a node separator $S$ of size $\tilde{O}(n/\delta)$ such that all SCCs in $G$ have diameter at most $\delta$. They can then use ES-trees with random sources to maintain the SCCs in $G \setminus S$ in total update time $\tilde{O}(m\delta)$. This leaves them with the task of computing how the vertices in $S$ might meld some of the SCCs in $G \setminus S$. They are able to do this in total update time $\tilde{O}(m|S|) = \tilde{O}(mn/\delta)$ by using an entirely different technique of <cit.>. Setting $\delta = \tilde{O}(\sqrt{n})$, they achieve the optimal trade-off between the two techniques: total update time $\tilde{O}(m\sqrt{n})$ in expectation.

We achieve our $\tilde{O}(m)$ total update time by entirely avoiding the technique of <cit.> for separately handling a small set of separator nodes, and instead using the graph hierarchy described above, where at each level we set $\delta$ to be polylog rather than $\tilde{O}(\sqrt{n})$.

We note that while our starting point is the same as <cit.>, using a hierarchy of separators forces us to take a different perspective on the function of a separator set. The reason is that it is simply not possible to ensure that at each level of the hierarchy, all SCCs have small diameter. To overcome this, we instead aim for separator sets that decompose the graph into SCCs that are small with respect to a different notion of distance. The rest of the overview briefly sketches this new perspective, while sweeping many additional technical challenges under the rug.

Refining the Hierarchy. So far, we only discussed how to maintain $\hat{G}_0$ efficiently by deleting many edges from $E_0$ and hence ensuring that SCCs in $\hat{G}_0$ have small diameter. To discuss our bottom-up approach, let us define our graphs $\hat{G}_i$ more precisely.

We maintain a separator hierarchy $\mathcal{S} = \{S_0, S_1, .. , S_{\lfloor \lg{n} \rfloor + 2}\}$ where $\hat{V}_0 = S_0 \supseteq S_1 \supseteq .. \supseteq S_{\lfloor \lg{n} \rfloor + 1} = S_{\lfloor \lg{n} \rfloor + 2} = \emptyset$, with $|S_i| \leq n/2^i$, for all $i \in [0, \lfloor \lg{n} \rfloor + 2]$ (see below that for technical reasons we need to define $S_{\lfloor \lg{n} \rfloor + 2}$ to define $\hat{G}_{\lfloor \lg{n} \rfloor + 1}$). Each set $S_i$ is a set of single-vertex nodes – i.e. nodes of the form $\{ v \}$ – that is monotonically increasing over time.

We can now more precisely define each edge set

\[
E_i = E(\textsc{Flatten}(S_{i})) \setminus E(\textsc{Flatten}(S_{i+1})).
\]

To avoid clutter, we abuse notation slightly referring henceforth to $\textsc{Flatten}(X)$ simply as $X$ if $X$ is a set of singleton sets and the context is clear. We therefore obtain

\begin{align*}
\hat{G}_i &=  \textsc{Condensation}((V, \bigcup_{j < i} E_j)) \;\cup\; E_{i} \\ &= \textsc{Condensation}(G \setminus E(S_{i})) \;\cup\; \left(E(S_i) \setminus E(S_{i+1})\right).
\end{align*}

In particular, note that $\hat{G}_i$ contains all the edges of $G$ except those in $E(S_{i+1})$; as we move up to level $\hat{G}_{i+1}$, we add the edges $E(S_{i+1}) \setminus E(S_{i+2})$. Note that if $s \in S_{i} \setminus S_{i+1}$, and our algorithm then adds $s$ to $S_{i+1}$, this will remove all edges incident to $s$ from $E_{i}$ and add them to $E_{i+1}$. Thus the fact that the sets $S_i$ used by the algorithm are monotonically increasing implies the desired property that edges only move up the hierarchy (remember that we add more vertices to $S_i$ due to new separators found on level $i-1$).

At a high-level, the idea of the hierarchy is as follows. Focusing on a level $i$, when the “distances” in some SCC of $\hat{G}_i$ get too large (for a notion of distance defined below), the algorithm will add a carefully chosen set of separator nodes $s_1, s_2, ..$ in $S_i$ to $S_{i+1}$. By definition of our hierarchy, this will remove the edges incident to the $s_i$ from $\hat{G}_i$, thus causing the SCCs of $\hat{G}_i$ to decompose into smaller SCCs with more manageable “distances”. We note that our algorithm always maintains the invariant that nodes added to $S_{i+1}$ were previously in $S_i$, which from the definition of our hierarchy, ensures that at all times the separator nodes in $S_{i+1}$ are single-vertex nodes in $\hat{V}_{i+1}$; this is because the nodes of $\hat{V}_{i+1}$ are the SCCs of $\hat{G}_i$, and $\hat{G}_i$ contains no edges incident to $S_{i+1}$.

Exploiting $S$-distances. For our algorithm, classic ES-trees are only useful to maintain SCCs in $\hat{G}_0$; in order to handle levels $i > 0$ we develop a new generalization of ES-trees that use a different notion of distance. This enables us to detect when SCCs are split in graphs $\hat{G}_i$ and to find separator nodes in $\hat{G}_i$ as discussed above more efficiently.

Our generalized ES-tree (GES-tree) can be seen as a combination of the classic ES-trees<cit.> and a data structure by Italiano<cit.> that maintains reachability from a distinguished source in a directed acyclic graph (DAG), and which can be implemented in total update time $O(m)$.

Let $S$ be some feedback vertex set in a graph $G = (V,E)$; that is, every cycle in $G$ contains a vertex in $S$. Then our GES-tree can maintain
$S$-distances and a corresponding shortest-path tree up to $S$-distance $\delta > 0$ from a distinguished source $X_i^r$ for some $r \in V$ in the graph $G$. (See <Ref> for the definition of $S$-distances.) This data structure can be implemented to take $O(m\delta)$ total update time.

Maintaining the SCCs in $\hat{G}_i$. Let us focus on maintaining SCCs in

\[
\hat{G}_i = \textsc{Condensation}(G \setminus E(S_{i})) \;\cup\; (E(S_{i}) \setminus E(S_{i+1})).\]

Since the condensation of any graph forms a DAG, every cycle in $\hat{G}_i$ contains at least one edge from the set $E(S_{i}) \setminus E(S_{i+1})$. Since $E(S_{i}) \setminus E(S_{i+1})$ is a set of edges that is incident to $S_i$, we have that $S_i$ forms a feedback node set of $\hat{G}_i$. Now consider the scheme described in the paragraphs above, but instead of running an ES in-tree and out-tree from each center $\textsc{Center}(X)$ for some SCC $X$, we run a GES in-tree and out-tree on $\hat{G}_i[X]$ that maintains the $S_i$-distances to depth $\delta$.  Using this GES, whenever a set $Y \subseteq X$ of nodes has $S_i$-distance $\Omega(\delta)$, we show that we can find a separator $S$ of size $O(\min\{|S_i \cap Y|, |S_i \cap (X \setminus Y)|\}\log n / \delta)$ that only consists of nodes that are in $\{\{s\} | s \in S_i\}$; we then add the elements of set $S$ to the set $S_{i+1}$, and we also remove the nodes $Y$ from the GES-tree, analogously to our discussion of regular ES-trees above. Note that adding $S$ to $S_{i+1}$ removes the edges $E(S)$ from $\hat{G}_i$; since we chose $S$ to be a separator, this causes $Y$ and $X \setminus Y$ to no longer be part of the same SCC in $\hat{G}_i$. Thus, to maintain the hierarchy, we must then split nodes in $\hat{G}_{i+1}$ into multiple nodes corresponding to the new SCCs in $\hat{G}_i$: $X \setminus (Y \;\cup\; S)$, $Y \setminus S$ and every single-vertex set in $S$ ($Y$ might not form a SCC but we then further decompose it after we handled the node split). This might cause some self-loops in $\hat{G}_{i+1}$ to become edges between the newly inserted nodes (resulting from the split) and needs to be handled carefully to embed the new nodes in the GES-trees maintained upon the SCC in $\hat{G}_{i+1}$ that $X$ is part of. Observe that this does not result in edge insertions but only remaps the endpoints of edges. Further observe that splitting nodes can only increase $S_{i+1}$-distance since when they were still contracted their distance from the center was equivalent. Since $S_{i+1}$-distance still might increase, the update to might trigger further changes in the graph $\hat{G}_{i+1}$.

Thus, overall, we ensure that all SCCs in $\hat{G}_i$ have $S_i$-diameter at most $O(\delta)$, and can hence be efficiently maintained by GES-trees. In particular, we show that whenever an SCC exceeds diameter $\delta$, we can, by moving a carefully chosen set of nodes in $S_i$ to $S_{i+1}$, remove a corresponding set of edges in $\hat{G}_i$, which breaks the large-$S_i$-diameter SCC into SCCs of smaller $S_i$-diameter.

Bounding the total update time. Finally, let us sketch how to obtain the total expected running time $O(m \log^4 n)$. We already discussed how by using random sources in GES-trees (analogously to the same strategy for ES-trees), we ensure that each node is expected to be in $O(\log n)$ GES-trees maintained to depth $\delta = O(\log^2 n)$.
Each such GES-tree is maintained in total update time $O(m\delta) = O(m\log^2n)$, so we have $O(m \log^3 n)$ total expected update time for each level, and since we have $O(\log n)$ levels, we obtain total expected update time $O(m\log^4 n)$. We point out that we have not included the time to compute the separators in our running time analysis; indeed, computing separators efficiently is one of the major challenges to building our hierarchy. Since implementing these subprocedures efficiently is rather technical and cumbersome, we omit their description from the overview but refer to section <ref> for a detailed discussion.

§ GENERALIZED ES-TREES

For our algorithm, we devise a new version of the ES-trees that maintains the shortest-path tree with regard to $S$-distances. We show that if $S$ is a feedback vertex set for $G$, that is a set such that every cycle in $G$ contains at least one vertex in $S$, then the data structure requires only $O(m\delta)$ total update time. Our fundamental idea is to combine classic ES-trees with techniques to maintain Single-Source Reachability in DAGs which can be implemented in linear time in the number of edges <cit.>. Since $\mathbf{dist}_G(r, v) = \mathbf{dist}_G(r, v, V)$  and $V$ is a trivial feedback vertex set, we have that our data structure generalizes the classic ES-tree. Since the empty set is a feedback vertex set for DAGs, our data structure also matches the time complexity of Italiano's data structure. We define the interface formally below.

Let $G=(V,E)$ be a graph and $S$ a feedback vertex set for $G$, $r \in V$ and $\delta > 0$. We define a generalized ES-tree $\mathcal{E}_r$ (GES) to be a data structure that supports the following operations:

* $\textsc{InitGES}(r, G, S, \delta)$: Sets the parameters for our data structure. We initialize the data structure and return the GES.

* $\textsc{Distance}(r ,v )$: $\forall v \in V$, if $\mathbf{dist}_G(r ,v, S) \leq \delta$, $\mathcal{E}_r$ reports $\mathbf{dist}_G(r ,v, S)$, otherwise $\infty$.

* $\textsc{Distance}(v ,r )$: $\forall v \in V$, if $\mathbf{dist}_G(v ,r, S) \leq \delta$, $\mathcal{E}_r$ reports $\mathbf{dist}_G(v ,r, S)$, otherwise $\infty$.

* $\textsc{Delete}(u,v)$: Sets $E \gets E \setminus \{(u,v)\}$.

* $\textsc{Delete}(V')$: For $V' \subseteq V$, sets $V \gets V \setminus V'$, i.e. removes the vertices in $V'$ and all incident edges from the graph $G$.

* $\textsc{GetUnreachableVertex}()$: Returns a vertex $v \in V$ with

\[
\max\{ \mathbf{dist}_G(r ,v, S), \mathbf{dist}_G(v, r, S)\} > \delta
\]

or $\bot$ if no such vertex exists.

The GES $\mathcal{E}_r$ as described in definition <ref> can be implemented with total initialization and update time $O(m \delta)$ and requires worst-case time $O(1)$ for each operation $\textsc{Distance}(\cdot)$ and $\textsc{GetUnreachableVertex}()$.

Here, we only sketch the proof idea and refer the reader to <cit.> for a full proof.

Consider a classic ES-tree with each edge weight $w(u,v)$ of an edge $(u,v)$ in $E_{out}(S)$ set to $1$ and all other edges of weight $0$. Then, the classic ES-tree analysis maintains with each vertex $v \in V$ the distance level $l(v)$ that expresses the current distance from $s$ to $v$. We also have a shortest-path tree $T$, where the path in the tree from $s$ to $v$ is of weight $l(v)$. Since $T$ is a shortest-path tree, we also have that for every edge $(u,v) \in E$, $l(v) \leq l(u) + w(u,v)$. Now, consider the deletion of an edge $(u,v)$ from $G$ that removes an edge that was in $T$. To certify that the level $l(v)$ does not have to be increased, we scan the in-going edges at $v$ and try to find an edge $(u', v) \in E$ such that $l(v) = l(u') + w(u', v)$. On finding this edge, $(u',v)$ is added to $T$. The problem is that if we allow $0$-weight cycles, the edge $(u',v)$ that we use to reconnect $v$ might come from a $u'$ that was a descendant of $v$ in $T$. This will break the algorithm, as it disconnects $v$ from $s$ in $T$. But we show that this bad case cannot occur because $S$ is assumed to be a feedback vertex set, so at least one of the vertices on the cycle must be in $S$ and therefore the out-going edge of this vertex must have weight $1$ contradicting that there exists any $0$-weight cycle. The rest of the analysis follows closely the classic ES-tree analysis.

To ease the description of our SCC algorithm, we tweak our GES implementation to work on the multi-graphs $\hat{G}_i$. We still root the GES at a vertex $r \in V$, but maintain the tree in $\hat{G}_i$ at $X_i^r$. The additional operations and their running time are described in the following Lemma whose proof is straight-forward and therefore omitted here (but can be found in <cit.>). Note that we now deal with nodes rather than vertices which makes the definition of $S$-distances ambiguous (consider for example a node containing two vertices in $S$). For this reason, we require $S \subseteq \{\{v\} | v \in V\} \cap \hat{V}$ in the Lemma below, i.e. that the nodes containing vertices in $S$ are single-vertex nodes. But as discussed in the paragraph “Refining the hierarchy" in the overview, our hierarchy ensures that every separator node $X \in S_i$ is always just a single-vertex node in $\hat{G}_i$. Thus this constraint can be satisfied by our hierarchy.

Say we are given a partition $\hat{V}$ of a universe $V$ and the graph $\hat{G}=(\hat{V}, E)$, a feedback node set $S \subseteq \{\{v\} | v \in V\} \cap \hat{V}$, a distinguished vertex $r \in V$, and a positive integer $\delta$. Then, we can run a GES $\mathcal{E}_{r}$ as in definition <ref> on $\hat{G}$ in time $O(m\delta + \sum_{X \in \hat{V}} E(X) \log X)$ supporting the additional operations:

* $\textsc{SplitNode}(X)$: the input is a set of vertices $X$ contained in node $Y \in \hat{V}$, such that either $E \cap (X \times Y \setminus X)$ or $E \cap (Y \setminus X \times X)$ is an empty set, which implies $X \not\rightleftarrows_{\hat{G} \setminus S} Y \setminus X$. We remove the node $Y$ in $\hat{V}$ and add node $X$ and $Y \setminus X$ to $\hat{V}$.

* $\textsc{Augment}(S')$: This procedure adds the nodes in $S'$ to the feedback vertex set $S$. Formally,

the input is a set of single-vertex sets $S' \subseteq \{\{v\} | v \in V\} \cap \hat{V}$. $\textsc{Augment}(S')$ then adds every $s \in S'$ to $S$.

We point out that we enforce the properties on the set $X$ in $\textsc{SplitNode}(X)$ in order to ensure that the set $S$ remains a feedback node set at all times.

§ INITIALIZING THE THE GRAPH HIERARCHY

We assume henceforth that the graph $G$ initially is strongly-connected. If the graph is not strongly-connected, we can run Tarjan's algorithm <cit.> in $O(m+n)$ time to find the SCCs of $G$ and run our algorithm on each SCC separately.

$\textsc{Preprocessing}(G, \delta)$

A strongly-connected graph $G=(V,E)$ and a parameter $\delta > 0$.
A hierarchy of sets $\mathcal{S} = \{ S_0, S_1, .., S_{\lfloor \lg{n} \rfloor + 2}\}$ and graphs $\hat{\mathcal{G}} = \{\hat{G}_0, \hat{G}_1, .. , \hat{G}_{\lfloor \lg{n} \rfloor + 1}\}$ as described in section <ref>. Further, each SCC $X$ in $\hat{G}_i$ for $i \leq \lfloor \lg n \rfloor + 2$, has a center $\textsc{Center}(X)$ such that for any $y \in X$, $\mathbf{dist}_{\hat{G}_{i}}(\textsc{Center}(X),y, S_{i}) \leq \delta/2$ and $\mathbf{dist}_{\hat{G}_{i}}(y,\textsc{Center}(X), S_{i}) \leq \delta/2$.

$ S_0 \gets V$
$ \hat{V}_0 \gets \{\{v\} | v \in V\}$
$ \hat{G}_0 \gets (\hat{V}_0, E)$
$i = 0 $ $ \lfloor \lg{n} \rfloor$
Find separator $S_{Sep}$ such that no two vertices in the same SCC in $\hat{G}_{i}$ have $S_i$-distance $\geq \delta/2$. $P$ is the collection of these SCCs.
$ (S_{Sep}, P) \gets \textsc{Split}(\hat{G}_i, S_{i}, \delta/2)$
$ S_{i+1} \gets S_{Sep} $
$\textsc{InitNewPartition}(P, i, \delta)$

Initialize the graph $\hat{G}_{i+1}$
$ \hat{V}_{i+1} \gets P$
$ \hat{G}_{i+1} \gets (\hat{V}_{i+1}, E)$

$S_{\lfloor \lg{n} \rfloor + 2} \gets \emptyset$

Our procedure to initialize our data structure is presented in pseudo-code in  <Ref>. We first initialize the level $0$ where $\hat{G}_0$ is simply $G$ with the vertex set $V$ mapped to the set of singletons of elements in $V$.

Let us now focus on an iteration $i$. Observe that the graph $\hat{G}_i$ initially has all edges in $E$ (by initializing each $\hat{G}_i$ in  <Ref> or <Ref>). Our goal is then to ensure that all SCCs in $\hat{G}_i$ are of small $S_i$-diameter at the cost of removing some of the edges from $\hat{G}_i$. Invoking the procedure $\textsc{Split}(\hat{G}_i, S_i, \delta/2)$ provides us with a set of separator nodes $S_{Sep}$ whose removal from $\hat{G}_i$ ensure that the $S_i$ diameter of all remaining SCCs is at most $\delta$. The set $P$ is the collection of all these SCCs, i.e. the collection of the SCCs in $\hat{G}_i \setminus E(S_{Sep})$.

<Ref> below describes in detail the properties satisfied by $\textsc{Split}(\hat{G}_i, S_i, \delta/2)$. In particular, besides the properties ensuring small $S_i$-diameter in the graph $\hat{G}_i \setminus E(S_{Sep})$ (properties <ref> and <ref>), the procedure also gives an upper bound on the number of separator vertices (property <ref>). Setting $\delta = 64 \lg^2 n$, clearly implies that $|S_{Sep}| \leq |S_i|/2$ and ensures running time $O(m \log^3 n)$.

$\textsc{Split}(\hat{G}_i, S_i, \delta/2)$ returns a tuple $(S_{Sep}, P)$ where $P$ is a partition of the node set $\hat{V}_i$ such that

* for $X \in P$, and nodes $u,v \in X$ we have  $\mathbf{dist}_{G \setminus E(S_{Sep})}(u,v,S) \leq \delta/2$, and

* for distinct $X, Y \in P$, with nodes $u \in X$ and $v \in Y$,   $u \not\rightleftarrows_{G \setminus E(S_{Sep})} v$, and

* $|S_{Sep}| \leq  \frac{32 \lg^2 n}{\delta} |S_i|$.

The algorithm runs in time $O\left(\delta m \lg n\right)$.

We then set $S_{i+1} = S_{Sep}$ which implicitly removes the edges $E(S_{i+1})$ from the graph $\hat{G}_i$. We then invoke the procedure $\textsc{InitNewPartition}(P, i, \delta)$, that is presented in algorithm <ref>. The procedure initializes for each $X \in P$ that corresponds to an SCC in $\hat{G}_i$ the GES-tree from a vertex $r \in \textsc{Flatten}(X)$ chosen uniformly at random on the induced graph $\hat{G}_i[X]$. Observe that we are not explicitly keeping track of the edge set $E_i$ but further remove edges implicitly by only maintaining the induced subgraphs of $\hat{G}_i$ that form SCCs. A small detail we want to point out is that each separator node $X \in S_{Sep}$ also forms its own single-node set in the partition $P$.

$\textsc{InitNewPartition}(P, i, \delta)$

A partition of a subset of the nodes $V$, and the level $i$ in the hierarchy.
Initializes a new ES-tree for each set in the partition on the induced subgraph $\hat{G}_i$.
$ X \in P $
Let $r$ be a vertex picked from $\textsc{Flatten}(X)$ uniformly at random.
$\textsc{Center}(X) \gets r$
Init a generalized ES-tree from $\textsc{Center}(X)$ to depth $\delta$.
$\mathcal{E}_r^i \gets \textsc{InitGES}(\textsc{Center}(X), \hat{G}_i[X], S_i, \delta)$

On returning to algorithm <ref>, we are left with initializing the graph $\hat{G}_{i+1}$. Therefore, we simply set $\hat{V}_{i+1}$ to $P$ and use again all edges $E$. Finally, we initialize $S_{\lfloor \lg n \rfloor + 2}$ to the empty set which remains unchanged throughout the entire course of the algorithm.

Let us briefly sketch the analysis of the algorithm which is more carefully analyzed in subsequent sections. Using again $\delta = 64 \lg^2 n$ and Lemma <ref>, we ensure that $|S_{i+1}| \leq |S_i|/2$, thus $|S_i| \leq n/2^i$ for all levels $i$. The running time of executing the $\textsc{Split}(\cdot)$ procedure $\lfloor \lg n \rfloor + 1$ times incurs running time $O(m \log^4 n)$ and initializing the GES-trees takes at most $O(m \delta)$ time on each level therefore incurring running time $O(m \log^3 n)$.

§ FINDING SEPARATORS

Before we describe how to update the data structure after an edge deletion, we want to explain how to find good separators since it is crucial for our update procedure. We then show how to obtain an efficient implementation of the procedure $\textsc{Split}(\cdot)$ that is the core procedure in the initialization.

Indeed, the separator properties that we want to show are essentially reflected in the properties of Lemma <ref>. For simplicity, we describe the separator procedures on simple graphs instead of our graphs $\hat{G}_i$; it is easy to translate these procedures to our multi-graphs
$\hat{G}_i$ because the separator procedures are not dynamic; they are only ever invoked on a fixed graph, and so we do not have to worry about node splitting and the like.

To gain some intuition for the technical statement of our separator properties stated in Lemma <ref>, consider that we are given a graph $G=(V,E)$, a subset $S$ of the vertices $V$, a vertex $r \in V$ and a depth $d$. Our goal is to find a separator $S_{Sep} \subseteq S$, such that every vertex in the graph $G \setminus S_{Sep}$ is either at $S$-distance at most $d$ from $r$ or cannot be reached from $r$, i.e. is separated from $r$.

We let henceforth $V_{Sep} \subseteq V$ denote the set of vertices that are still reachable from $r$ in $G \setminus S_{Sep}$ (in particular there is no vertex $S_{Sep}$ contained in $V_{Sep}$ and $r \in V_{Sep}$). Then, a natural side condition for separators is to require the set $S_{Sep}$ to be small in comparison to the smaller side of the cut, i.e. small in comparison to $\min\{|V_{Sep}|, |V \setminus (V_{Sep} \;\cup\; S_{Sep})|\}$.

Since we are concerned with $S$-distances, we aim for a more general guarantee: we want the set $S_{Sep}$ to be small in comparison to the number of $S$ vertices on any side of the cut, i.e. small in comparison to $\min\{|V_{Sep} \cap S|, |(V \setminus (V_{Sep} \;\cup\; S_{Sep})) \cap S|\}$. This is expressed in property <ref> of the Lemma.

There exists a procedure $\textsc{OutSep}(r, G, S, d)$ (analogously $\textsc{InSep}(r, G, S, d)$) where $G=(V,E)$ is a graph, $r \in V$ a root vertex, $S \subseteq V$ and $d$ a positive integer. The procedure computes a tuple $(S_{Sep}, V_{Sep})$ such that

* $S_{Sep} \subseteq S$, $V_{Sep} \subseteq V$, $S_{Sep} \cap V_{Sep} = \emptyset$, $r \in V_{Sep}$,

*  $\forall v \in V_{Sep} \;\cup\; S_{sep}$, we have $\mathbf{dist}_G(r,v,S) \leq d$ (analogously $\mathbf{dist}_G(v,r,S) \leq d$ for $\textsc{InSep}(r, G, S, d)$),

\[
|S_{Sep}| \leq \frac{\min\{|V_{Sep}\cap S|, | (V \setminus (S_{Sep} \;\cup\; V_{Sep})) \cap S|\} 2\log{n}}{d},\]

* for any $x \in V_{Sep}$ and $y \in V \setminus (S_{Sep} \;\cup\; V_{Sep})$, we have $u \not\leadsto_{G \setminus E(S_{Sep})} v$ (analogously $v \not\leadsto_{G \setminus E(S_{Sep})} u$ for $\textsc{InSep}(r, G, S, d)$).

The running time of both $\textsc{OutSep}(\cdot)$ and $\textsc{InSep}(\cdot)$ can be bounded by $O(E(V_{Sep}))$.

Again, we only sketch the proof idea and refer the reader to <cit.> for a full proof.

To implement procedure $\textsc{OutSep}(r, G, S, d)$, we start by computing a BFS at $r$. Here, we assign edges in $E_{out}(S)$ again weight $1$ and all other edges weight $0$ and say a layer consists of all vertices that are at same distance from $r$. To find the first layer, we can use the graph $G \setminus E_{out}(S)$ and run a normal BFS from $r$ and all vertices reached form the first layer $L_0$. We can then add for each edge $(u,v) \in E_{out}(S)$ with $u \in L_0$ the vertex $v$ to $L_1$ if it is not already in $L_0$. We can then contract all vertices visited so far into a single vertex $r'$ and repeat the procedure described for the initial root $r$. It is straight-forward to see that the vertices of a layer that are also in $S$ form a separator of the graph. To obtain a separator that is small in comparison to $|V_{Sep} \cap S|$, we add each of the layers $0$ to $d/2$ one after another to our set $V_{Sep}$, and output the index $i$ of the first layer that grows the set of $S$-vertices in $V_{Sep}$ by factor less than $(1+\frac{2 \log n}{d})$. We then set $S_{Sep}$ to be the vertices in $S$ that are in layer $i$. If the separator is not small in comparison to $| (V \setminus (S_{Sep} \;\cup\; V_{Sep})) \cap S|$, we grow more layers and output the first index of a layer such that the separator is small in comparison to $| (V \setminus (S_{Sep} \;\cup\; V_{Sep})) \cap S|$. This layer must exist and is also small in comparison to $|V_{Sep} \cap S|$. Because we find our separator vertices $S_{Sep}$ using a BFS from $r$, a useful property of our separator is that all the vertices in $S_{Sep}$ and $V_{Sep}$ are within bounded distance from $r$.

Finally, we can ensure that the running time of the procedure is linear in the size of the set $E(V_{Sep})$, since these are the edges that were explored by the BFS from root $r$.

Let us now discuss the procedure $\textsc{Split}(G,S,d)$ that we already encountered in section <ref> and whose pseudo-code is given in algorithm <ref>. Recall that the procedure computes a tuple $(S_{Split}, P)$ such that the graph $G \setminus E(S_{Split})$ contains no SCC with $S$-diameter larger $d$ and where $P$ is the collection of all SCCs in the graph $G \setminus E(S_{Split})$.

$\textsc{Split}(G, S, d)$

A graph $G=(V,E)$, a set $S \subseteq V$ and a positive integer $d$.
Returns a tuple $(S_{Split}, P)$, where $S_{Split} \subseteq S$ is a separator such that no two vertices in the same SCC in $G \setminus E(S)$ have $S$-distance greater than $d$. $P$ is the collection of these SCCs.

$S_{Split} \gets \emptyset; P \gets \emptyset; G' \gets G;$

$G' \neq \emptyset$
Pick an arbitrary vertex $r$ in $V$.
Run in parallel $\textsc{OutSep}(r, G', S, d/16)$ and $\textsc{InSep}(r, G', S, d/16)$ and let $(S_{Sep}, V_{Sep})$ be the tuple returned by the first subprocedure that finishes.

()$|V_{Sep}| \leq \frac{2}{3}|V|$
$(S'_{Sep}, V'_{Sep}) \gets (S_{Sep}, V_{Sep})$
Run the separator procedure that was aborted in line <ref> until it finishes and let the tuple returned by this procedure be $(S'_{Sep}, V'_{Sep})$.

()$|V'_{Sep}| \leq \frac{2}{3}|V|$
$(S_{Small}, P_{Small}) \gets \textsc{Split}(G'[V'_{Sep}], V'_{Sep} \cap S, d)$
$S_{Split} \gets S_{Split} \;\cup\; S_{Small} \;\cup\; S'_{Sep}$
$P \gets P \;\cup\; P_{Small} \;\cup\; \{ \{s\} | s \in S'_{Sep}\})$
$G' \gets G'[V \setminus (V'_{Sep} \;\cup\; S'_{Sep})]$
Init a generalized ES-tree from $r$ to depth $d/2$.
$\mathcal{E}_r^i \gets \textsc{InitGES}(r, G', S, d/2)$
Find a good separator for every vertex that is far from $r$.
()   $(v \gets \mathcal{E}_r^i.\textsc{GetUnreachableVertex}()) \neq \bot$
$\mathcal{E}_r^i.\textsc{Distance}(r,v) > d/2$
$(S''_{Sep}, V''_{Sep}) \gets \textsc{InSep}(v,G', S, d/4)$
(*[h]If $\mathcal{E}_r^i.\textsc{Distance}(v,r) > d/2$)
$(S''_{Sep}, V''_{Sep}) \gets \textsc{OutSep}(v,G', S, d/4)$

$\mathcal{E}_r.\textsc{Delete}(S''_{Sep} \;\cup\; V''_{Sep})$

$(S'''_{Sep}, P''') \gets \textsc{Split}( G[V''_{Sep}] , V''_{Sep} \cap  S , d)$
$S_{Split} \gets S_{Split} \;\cup\; S''_{Sep} \;\cup\; S'''_{Sep}$
$P \gets P \;\cup\; P''' \;\cup\; \{ \{s\} | s \in S''_{Sep}\})$

$P \gets P \;\cup\; \{\mathcal{E}_r.\textsc{GetAllVertices}()\}$
$G' \gets \emptyset$

$(S_{Split}, P)$

Let us sketch the implementation of the procedure $\textsc{Split}(G,S,d)$. We first pick a vertex and invoke the procedures $\textsc{OutSep}(r, G', S, d/4)$ and $\textsc{InSep}(r, G', S, d/4)$ to run in parallel, that is the operations of the two procedures are interleaved during the execution. If one of these subprocedures returns and presents a separator tuple $(S_{Sep}, V_{Sep})$, the other procedure is aborted and the tuple $(S_{Sep}, V_{Sep})$ is returned. If $|V_{Sep}| \leq \frac{2}{3}|V|$, then we conclude that the separator function only visited a small part of the graph. Therefore, we use the separator subsequently, but denote the tuple henceforth as $(S'_{Sep},V'_{Sep})$. Otherwise, we decide the separator is not useful for our purposes. We therefore return to the subprocedure we previously aborted and continue its execution. We then continue with the returned tuple $(S'_{Sep}, V'_{Sep})$.

From there on, there are two possible scenarios. The first scenario is that the subprocedure producing $(S'_{Sep}, V'_{Sep})$ has visited a rather small fraction of the vertices in $V$ (line <ref>); in this case, we have pruned away a small number of vertices $V'_{Sep}$ while only spending time proportional to the smaller side of the cut, so we can simply recurse on $V'_{Sep}$. We also have to continue pruning away vertices from the original set $V$, until we have either removed all vertices from $G$ by finding these separators and recursing, or until we enter the else-case (line <ref>).

The else-case in line <ref> is the second possible scenario:  note that in this case we must have entered the else-case in line <ref> and had both the $\textsc{InSep}(\cdot)$ and $\textsc{OutSep}(\cdot)$ explore the large side of the cut. Thus we cannot afford to simply recurse on the smaller side of the cut $V \setminus V'_{sep}$, as we have already spent time $|V'_{sep}| > |V \setminus V'_{sep}|$. Thus, for this case we use a different approach. We observe that because we entered the else-case in line <ref> and since we entered the else-case <ref>, we must have had that $|V_{Sep}| \geq \frac{2}{3}|V|$ and that $|V'_{Sep}| \geq \frac{2}{3}|V|$. We will show that in this case, the root $r$ must have small $S$-distance to and at least $\frac{1}{3}|V|$ vertices. We then show that this allows us to efficiently prune away at most $\frac{2}{3}|V|$ vertices from $V$ at large $S$-distance to or from $r$. We recursively invoke $\textsc{Split}(\cdot)$ on the induced subgraphs of vertex sets that we pruned away.

We analyze the procedure in detail in multiple steps, and summarize the result in Lemma <ref> that is the main result of this section. Let us first prove that if the algorithm enters the else-case in line <ref> then we add an SCC of size at least $\frac{1}{3}|V|$ to $P$.

If the algorithm enters line <ref> then the vertex set returned by the procedure $\mathcal{E}_r.\textsc{GetAllVertices}()$ in line <ref> is of size at least $\frac{1}{3}|V|$.

Observe first that since we did no enter the if-case in line <ref>, that $|V_{Sep}| > \frac{2}{3}|V|$ and $|V'_{Sep}| > \frac{2}{3}|V|$ (since we also cannot have entered the if case in line <ref>).

Since we could not find a sufficiently good separator in either direction, we certified that the $S$-out-ball from $r$ defined

\[
B_{out}(r) = \{ v \in V | \mathbf{dist}_G(r , v, S) \leq d/16\}
\]

has size greater than $\frac{2}{3}|V|$, and that similarly, the $S$-in-ball $B_{in}(r)$ of $r$ has size greater than $\frac{2}{3}|V|$. This implies that

\[
|B_{out}(r) \cap B_{in}(r)| > \frac{1}{3}|V|.
\]

Further, we have that every vertex on a shortest-path between $r$ and a vertex $v \in B_{out}(r) \cap B_{in}(r)$ has a shortest-path from and to $r$ of length at most $d/16$. Thus the $S$-distance between any pair of vertices in $B_{out}(r) \cap B_{in}(r)$ is at most $d/8$. Now, let $SP$ be the set of all vertices that are on a shortest-path w.r.t. $S$-distance between two vertices in $B_{out}(r) \cap B_{in}(r)$. Clearly, $B_{out}(r) \cap B_{in}(r) \subseteq SP$, so $|SP| \geq |V|/3$. It is also easy to see that $G[SP]$ has $S$-diameter at most $d/4$.

At this point, the algorithm repeatedly finds a vertex $v$ that is far from $r$ and finds a separator from $v$. We will now show that the part of the cut containing $v$ is always disjoint from $SP$; since $|SP| > |V|/3$, this implies that at least $|V|/3$ vertices remain in $\mathcal{E}_r$.

Finally, consider some vertex $v$ chosen in line <ref>. Let us say that we now run $\textsc{InSep}(v,G',S,d/4)$; the case where we run $\textsc{OutSep}(v,G',S,d/4)$ is analogous. Now, by property <ref> in Lemma <ref>, every $s \in S_{Sep}$ has $\mathbf{dist}(s,v,S) \leq d/4$. Thus, since we only run the InSep if we have $\mathbf{dist}(r,v,S) > d/2$, we must have $\mathbf{dist}(r,s,S) > d/4$.

We point out that claim <ref> implies that $\textsc{Split}(\cdot)$ only recurses on disjoint subgraphs containing at most a $2/3$ fraction of the vertices of the given graph. To see this, observe that we either recurse in line <ref> on $G'[V'_{Sep}]$ after we explicitly checked whether $|V'_{Sep}| \leq \frac{2}{3}|V|$ in the if-condition, or we recurse in line <ref> on the subgraph pruned from the set of vertices that $\mathcal{E}_r$ was initialized on. But since by claim <ref> the remaining vertex set in $\mathcal{E}_r$ is of size at least $|V|/3$, the subgraphs pruned away can contain at most $\frac{2}{3}|V|$ vertices.

We can use this observation to establish correctness of the $\textsc{Split}(\cdot)$ procedure.

$\textsc{Split}(G, S, d)$ returns a tuple $(S_{Sep}, P)$ where $P$ is a partition of the vertex set $V$ such that

* for $X \in P$, and vertices $u,v \in X$ we have  $\mathbf{dist}_{G \setminus E(S_{Sep})}(u,v,S) \leq d$, and

* for distinct $X, Y \in P$, with vertices $u \in X$ and $v \in Y$,   $u \not\rightleftarrows_{G \setminus E(S_{Sep})} v$, and

* $|S_{Split}| \leq  \frac{32 \log n}{d} \sum_{X \in P}  \lg (n  / |X \cap S|) |X \cap S|$.

Let us start with the first two properties which we prove by induction on the size of $|V|$ where the base case $|V|=1$ is easily checked. For the inductive step, observe that each SCC $X$ in the final collection $P$ was added to $P$ in line <ref>, <ref> or <ref>. We distinguish by 3 cases:

* a vertex $s$ was added as singleton set after appearing in a separator $S_{Sep}$ but then $\{s\}$ is strongly-connected and $s$ cannot reach any other vertex in $G \setminus E(S_{Sep})$ since it has no out-going edges, or

* an SCC $X$ was added as part of a collection $P'''$ in line  <ref>. But then we have that the collection $P'''$ satisfies the properties in $G[V''_{Sep}]$ by the induction hypothesis and since $V''_{Sep}$ was a cut side and $S''_{Sep}$ added to $S_{out}$, we have that there cannot be a path to and from any vertex in $G \setminus E(S_{out})$, or

* we added the non-trivial SCC $X$ to $P$ after constructing an GES-tree from some vertex $r \in X$ and after pruning each vertex at $S$-distance to/from $r$ larger than $d/2$ (see the while loop on line <ref>). But then each vertex that remains in $X$ can reach $r$ within $S$-distance $d/2$ and is reached from $r$ within distance $d/2$ implying that any two vertices $u,v \in X$ have a path from $u$ to $v$ of $S$-distance at most $d$.

Finally, let us upper bound the number of vertices in $S_{Split}$. We use a classic charging argument and argue that each time we add a separator $S_{Sep}$ to $S_{Split}$ with sides $V_{Sep}$ and $V \setminus (V_{Sep} \;\cup\; S_{Sep})$ at least one of these sides contains at most half the $S$-vertices in $V \cap S$. Let $X$ be the smaller side of the cut (in term of $S$-vertices) then by property <ref> from Lemma <ref>, we can charge each $S$ vertex in $X$ for $\frac{32 \log{n}}{d}$ separator vertices (since we invoke $\textsc{OutSep}(\cdot)$ and $\textsc{InSep}(\cdot)$ with parameter at least $d/16$).

Observe that once we determined that a separator $S_{Sep}$ that is about to be added to $S_{Split}$ in line <ref> or <ref>, we only recurse on the induced subgraph $G'[V_{Sep}]$ and let the graph in the next iteration be $G'[V \setminus (V_{Sep} \;\cup\; S_{Sep})$.

Let $X$ be an SCC in the final collection $P$. Then each vertex $v \in X$ can only have been charged at most $\lg (n  - |X \cap S|)$ times. The Lemma follows.

It remains to bound the running time. Before we bound the overall running time, let us prove the following claim on the running time of invoking the separator procedures in parallel.

We spend $O(E(V'_{Sep} \;\cup\; S'_{Sep}))$ time to find a separator in line <ref> or <ref>.

Observe that we run $\textsc{OutSep}(r, G', S, d/16)$ and $\textsc{InSep}(r, G', S, d/16)$ in line <ref> in parallel. Therefore, when we run them, we interleave their machine operations, computing one operation from $\textsc{OutSep}(r, G', S, d/16)$ and then one operation from $\textsc{InSep}(r, G', S, d/16)$ in turns. Let us assume that $\textsc{OutSep}(r, G', S, d/16)$ is the first subprocedure that terminates and returns tuple $(S_{Sep}, V_{Sep})$. Then, by Lemma <ref>, the subprocedure used $O(E(V_{Sep} \;\cup\; S_{Sep}))$ time. Since the subprocedure $\textsc{InSep}(r, G', S, d/16)$ ran at most one more operation than $\textsc{OutSep}(r, G', S, d/16)$, it also used $O(E(V_{Sep} \;\cup\; S_{Sep}))$ operations. If $\textsc{InSep}(r, G', S, d/16)$ finishes first, a symmetric argument establishes the same bounds. The overhead induced by running two procedures in parallel can be made constant.

Since assignments take constant time, the claim is vacuously true by our discussion if the if-case in line <ref> is true. Otherwise, we compute a new separator tuple by continuing the execution of the formerly aborted separator subprocedure. But by the same argument as above, this subprocedure's running time now clearly dominates the running time of the subprocedure that finished first in line <ref>. The time to compute $(S'_{Sep}, V'_{Sep})$ is thus again upper bounded by $O(E(V'_{Sep}))$ by Lemma <ref>, as required.

Finally, we have established enough claims to prove Lemma <ref>.

The procedure $\textsc{Split}(G, S, d)$ returns a tuple $(S_{Split}, P)$ where $P$ is a partition of the vertex set $V$ such that

* for $X \in P$, and vertices $u,v \in X$ we have  $\mathbf{dist}_{G \setminus E(S_{Split})}(u,v,S) \leq d$, and

* for distinct $X, Y \in P$, with vertices $u \in X$ and $v \in Y$,   $u \not\rightleftarrows_{G \setminus E(S_{Split})} v$, and

* $|S_{Split}| \leq  \frac{32 \log n}{d} \sum_{X \in P}  \lg (n  - |X \cap S|) |X \cap S|$

The algorithm runs in time $O\left(d \sum_{X \in P} (1 + \lg( n  - |X|)) E(X) \right)$.

Since correctness was established in Lemma <ref>, it only remains to bound the running time of the procedure. Let us first bound the running time without recursive calls to procedure $\textsc{Split}(G, S,d)$. To see that we only spend $O(|E(G)| d)$ time in $\textsc{Split}(G, S,d)$ excluding recursive calls, observe first that we can find each separator tuple $(S'_{Sep}, V'_{Sep})$ in time $O(E(V'_{Sep}))$ by claim <ref>. We then, either recurse on $G'[V'_{Sep}])$ and remove the vertices $V'_{Sep} \;\cup\; S'_{Sep}$ with their incident edges from $G'$ or we enter the else-case (line <ref>). Clearly, if our algorithm never visits the else-case, we only spend time $O(|E(G)|)$ excluding the recursive calls since we immediately remove the edge set that we found in the separator from the graph.

We further observe that the running time for the GES-tree can be bounded by $O(|E(G)| d)$. The time to compute the separators to prune vertices away from the GES-tree is again combined at most $O(|E(G)|)$ by Lemma <ref> and the observation that we remove edges from the graph $G$ after they were scanned by one such separator procedure.

We already discussed that claim <ref> implies that we only recurse on disjoint subgraphs with at most $\frac{2}{3}|V|$ vertices. We obtain that each vertex in a final SCC $X$ in $P$ participated in at most $O(\log( n - |X|))$ levels of recursion and so did its incident edges hence we can bound the total running time by $O\left(d \sum_{X \in P} (1 + \log( n  - |X|)) E(X) \right)$.

§ HANDLING DELETIONS

Let us now consider how to process the deletion of an edge $(u,v)$ which we describe in pseudo code in algorithm <ref>. We fix our data structure in a bottom-up procedure where we first remove the edge $(u,v)$ if it is contained in any induced subgraph $\hat{G}_i[X]$ from the GES $\mathcal{E}_{\textsc{Center}(X)}$.

An edge $(u,v) \in E$.
Updates the data structure such that queries for the graph $G \setminus \{ (u,v)\}$ can be answered in constant time.

$i = 0 $ $ \lfloor \log{n} \rfloor$
If there exists an $X \in \hat{V}_{i+1}$ with $u,v \in X$

there exists an $X \in \hat{V}_{i+1}$ with $\mathcal{E}_{\textsc{Center}(X)}.\textsc{GetUnreachable}() \neq \bot$
$X' \gets \mathcal{E}_{\textsc{Center}(X)}.\textsc{GetUnreachable}()$

Find a separator from $X'$ depending on whether $X'$ is far to reach from $r$ or the other way around.
$\mathcal{E}_{\textsc{Center}(X)}.\textsc{Distance}(\textsc{Center}(X),X') > \delta$
$(S_{Sep}, V_{Sep}) \gets \textsc{InSep}(X', \hat{G}_i[X], X \cap S_i, \delta/2)$

(*[h]$\mathcal{E}_{\textsc{Center}(X)}.\textsc{Distance}(X', \textsc{Center}(X)) > \delta$)
$(S_{Sep} , V_{Sep}) \gets \textsc{OutSep}(X' , \hat{G}_i[X] , X \cap S_i , \delta/2)$

If the separator is chosen such that $V_{Sep}$ is small, we have a good separator, therefore we remove $V_{Sep}$ from $\mathcal{E}_r$ and maintain the SCCs in $\hat{G}_{i}[V_{Sep}]$ separately. Otherwise, we delete the entire GES $\mathcal{E}_{\textsc{Center}(X)}$ and partition the graph with a good separator.
$|\textsc{Flatten}(V_{Sep})| \leq \frac{2}{3}|\textsc{Flatten}(X)|$
$\mathcal{E}_{\textsc{Center}(X)}.\textsc{Delete}(V_{Sep}\;\cup\; S_{Sep})$
$(S'_{Sep}, P') \gets \textsc{Split}(\hat{G}_i[V_{Sep}], V_{Sep} \cap S_i, \delta/2)$
$S''_{Sep} \gets S_{Sep} \;\cup\; S'_{Sep}$
$P'' \gets P' \;\cup\;  S_{Sep}$

$(S''_{Sep}, P'') \gets \textsc{Split}(\hat{G}_i[X], X \cap S_i, \delta/2)$

After finding the new partitions, we init them, execute the vertex splits on the next level and add the separator vertices.
$\textsc{InitNewPartition}(P'', i, \delta)$

$Y \in P''$

$S_{i+1} \gets S_{i+1} \;\cup\; S''_{Sep}$

Then, we check if any GES $\mathcal{E}_{\textsc{Center}(X)}$ on a subgraph $\hat{G}_i[X]$ contains a node that became unreachable due to the edge deletion or the fixing procedure on a level below. Whilst there is such a GES $\mathcal{E}_{\textsc{Center}(X)}$, we first find a separator $S_{Sep}$ from $X'$ in lines <ref> or <ref>. We now consider two cases based on the size of the set $\textsc{Flatten}(V_{Sep})$. Whilst focusing on the size of $\textsc{Flatten}(V_{Sep})$ instead of the size of $V_{Sep}$ seems like a minor detail, it is essential to consider the underlying vertex set instead of the node set, since the node set can be further split by node split updates from lower levels.

Now, let us consider the first case, when the set $V_{Sep}$ separated by $S_{Sep}$ is small (with regard to $\textsc{Flatten}(V_{Sep})$); in this case, we simply prune $V_{Sep}$ from our tree by adding $S_{Sep}$ to $S_{i+1}$, and then invoke $\textsc{Split}(\hat{G}_i[V_{Sep}], V_{Sep} \cap S_i, \delta/2)$ to get a collection of subgraphs $P'$ where each subgraph $Y \in P'$ has every pair of nodes $A, B \in Y$ at $S_{i}$-distance $\delta/2$. (We can afford to invoke $\textsc{Split}$ on the vertex set $V_{Sep}$ because we can afford to recurse to on the smaller side of a cut.)

The second case is when $V_{Sep}$ is large compared to the number of vertices in node set of the GES-tree. In this case we do not add $S_{Sep}$ to $S_{i+1}$. Instead we we declare the GES-tree $\mathcal{E}_{\textsc{Center}(X)}$ invalid, and delete the entire tree. We then partition the set $X$ that we are working with by invoking the $\textsc{Split}$ procedure on all of $X$. (Intuitively, this step is expensive, but we will show that whenever it occurs, there is a constant probability that the graph has decomposed into smaller SCCs, and we have thus made progress.)

Finally, we use the new partition and construct on each induced subgraph a new GES-tree at a randomly chosen center. This is done by invoking $\textsc{InitNewPartition}(P', i, \delta)$ that was presented in subsection <ref>. We then apply the updates to the graph $\hat{G}_{i+1}$ using the GES-tree operations defined in Lemma <ref>. Note, that we include the separator vertices as singleton sets in the partition and therefore invoke $\mathcal{E}_X.\textsc{SplitNode}(\cdot)$ on each singleton before invoking $\mathcal{E}_X.\textsc{Augment}(S''_{Sep})$ which ensures that the assumption from Lemma <ref> is satisfied. As in the last section, let us prove the following two Lemmas whose proofs will further justify some of the details of the algorithm.

We start by showing that because we root the GES-tree for SCC $X$ at a random root $r$, if the GES-tree ends up being deleted in <ref> in algorithm <ref>, this means that with constant probability $X$ has decomposed into smaller SCCs, and so progress has been made.

lemmaparticipation[c.f. also <cit.>, Lemma 13]

Consider an GES $\mathcal{E}_r = \mathcal{E}_{\textsc{Center}(X)}$ that was initialized on the induced graph of some node set $X_{Init}$, with $X \subseteq X_{Init}$, and that is deleted in line <ref> in algorithm <ref>. Then with probability at least $\frac{2}{3}$, the partition $P''$ computed in line <ref> satisfies that each $X' \in P''$ has $|\textsc{Flatten}(X')| \leq \frac{2}{3}|\textsc{Flatten}(X_{Init})|$.

Let $i$ be the level of our hierarchy on which $\mathcal{E}_{r}$ was initialized, i.e. $\mathcal{E}_{r}$ was initialized on graph $\hat{G}_i[X_{Init}]$, and went up to depth $\delta$ with respect to $S_i$-distances (see Algorithm <ref>).

Let $u_1, u_2, ..$ be the sequence of updates since the GES-tree $\mathcal{E}_r$ was initialized that were either adversarial edge deletions, nodes added to $S_i$ or node splits in the graph $\hat{G}_i[X_{Init}]$. Observe that this sequence is independent of how we choose our random root $r$, since they occur at a lower level, and so do not take any GES-trees at level $i$ into account. Recall, also, that the adversary cannot learn anything about $r$ from our answers to queries because the SCCs of the graph are objective, and so do not reveal any information about our algorithm. We refer to the remaining updates on $\hat{G}_i[X_{Init}]$ as separator updates, which are the updates adding nodes to $S_{i+1}$ and removing edges incident to $S_{i+1}$ or between nodes that due to such edge deletions are no longer strongly-connected. We point out that the separator updates are heavily dependent on how we chose our random source. The update sequence that the GES-tree undergoes up to its deletion in line <ref> is a mixture of the former updates that are independent of our chosen root $r$ and the separator updates.

Let $G^j$ be the graph $\hat{G}_i$ after the update sequence $u_1, u_2, ..., u_j$ is applied. Let $X_{max}^j$ be the component of $S_i$-diameter at most $\delta/2$ that maximizes the cardinality of $\textsc{Flatten}(X_{max}^j)$ in $G^j$. We choose $X_{max}^j$ in this way because we want to establish an upper bound on the largest SCC of $S_i$-diameter at most $\delta/2$ in $G^j$. We then show that that if a randomly chosen source deletes a GES-tree (see line <ref>) after $j$ updates, then there is a good probability that $X_{max}^j$ is small. Then by the guarantees of Lemma <ref>, the $\textsc{Split}(\cdot)$ procedure in line <ref> partitions the vertices into SCCs $X'$ of $S_i$-diameter at most $\delta/2$, which all have small $|\textsc{Flatten}(X')|$ because $X_{max}^j$ is small.

More precisely, let $G^j_r$, be the graph is obtained by applying all updates up to update $u_j$ to $\hat{G}_i[X_{Init}]$; here we include the updates $u_1, ..., u_j$, as well as all separator updates up to the time when $u_j$ takes place. (Observe that $G^j$ is independent from the choice of $r$, but $G^j_r$ is not.) Let $X_{max, r}^j$ be the component of $S_i$-diameter at most $\delta/2$ that maximizes the cardinality of $\textsc{Flatten}(X^j_{max, r})$ in this graph $G^j_r$. It is straight-forward to see that since $S_i$-distances can only increase due to separator updates, we have $|\textsc{Flatten}(X_{max, r}^j)| \leq |\textsc{Flatten}(X_{max}^j)|$ for any $r$. Further $|\textsc{Flatten}(X_{max, r}^j)|$ upper bounds the size of any component $X' \in P''$, i.e. $|\textsc{Flatten}(X')| \leq |\textsc{Flatten}(X_{max, r}^j)|$ if the tree $\mathcal{E}_r$ is deleted in line <ref> while  handling update $u_j$; the same bound holds if $\mathcal{E}_r$ is deleted after update $u_j$, because the cardinality of $\textsc{Flatten}(X_{max, r}^j)$ monotonically decreases in $j$, i.e. $|\textsc{Flatten}(X_{max, r}^{j})| \leq |\textsc{Flatten}(X_{max, r}^{j-1})|$ since updates can only increase $S_i$-distances.

Now, let $k$ be the index, such that

\[
|\textsc{Flatten}(X_{max}^k)| \leq \frac{2}{3}|\textsc{Flatten}(X_{Init})| < |\textsc{Flatten}(X_{max}^{k-1})|.
\]

i.e. $k$ is chosen such that after the update sequence $u_1, u_2,..., u_{k}$ were applied to $\hat{G}_i[X_{Init}]$, there exists no SCC $X$ in $G^k$ of diameter at most $\delta/2$ with $|\textsc{Flatten}(X)| > \frac{2}{3}|\textsc{Flatten}(X_{Init})|$.

In the remainder of the proof, we establish the following claim: if we chose some vertex $r \in \textsc{Flatten}(X^{k-1}_{max})$, then the GES-tree would not be been deleted before update $u_k$ took place. Before we prove this claim, let us point out that this implies the Lemma: observe that by the independence of how we choose $r$ and the update sequence $u_1, u_2, ..$, we have that

\[
Pr[r \in X_{max}^{k-1} | u_1, u_2, ..] = Pr[r \in X_{max}^{k-1}] = \frac{|\textsc{Flatten}(X_{max}^{k-1})|}{|\textsc{Flatten}(X_{Init})} > \frac{2}{3}
\]

where the before-last equality follows from the fact that we choose the root uniformly at random among the vertices in $\textsc{Flatten}(X_{Init})$. Thus, with probability at least $\frac{2}{3}$, we chose a root whose GES-tree is deleted during or after the update $u_k$ and therefore the invoked procedure $\textsc{Split}(\cdot)$ ensures that every SCC $X' \in P''$ satisfies $|\textsc{Flatten}(X')| \leq  |\textsc{Flatten}(X_{max}^k)| \leq \frac{2}{3}|\textsc{Flatten}(X_{Init})|$, as required.

Now, let us prove the final claim. We want to show that if $r \in X^{k-1}_{max}$, then the GES-tree would not have been deleted before update $u_k$. To do so, we need to show that even if we include the separator updates, the SCC containing $r$ continues to have size at least $\frac{2}{3}|\textsc{Flatten}(X_{Init})|$ before update $u_k$. In particular, we argue that before update $u_k$, none of the separator updates decrease the size of $X^{k-1}_{max}$. The reason is that the InSep computed in Line
<ref> of Algorithm <ref> is always run from a node $X$ whose $S_i$-distance from $r$ is at least $\delta$. (The argument for an OutSep in Line <ref> is analogous.)
Now, the InSep from $X$ is computed up to $S_i$-distance $\delta/2$, so by Property <ref> of Lemma <ref>, we have that all nodes pruned away from the component have $S_i$-distance at most $\delta/2$ to $X$; this implies that these nodes have $S_i$-distance more than $\delta/2$ from $r$, and so cannot be in $X^{k-1}_{max}$, because $X^{k-1}_{max}$ was defined to have $S_i$-diameter at most $\delta/2$. Thus none of the separator updates affect $X^{k-1}_{max}$ before update $u_k$, which concludes the proof of the Lemma.

Next, let us analyze the size of the sets $S_i$. We analyze $S_i$ using the inequality below in order to ease the proof of the Lemma. We point out that the term $\lg(n -|X \;\cup\; S_i|)$ approaches $\lg n$ as the SCC $X$ splits further into smaller pieces. Our Lemma can therefore be stated more easily, see therefore Corollary <ref>.

During the entire course of deletions our algorithm maintains

\begin{align}
|S_0| &= n                    & \\
|S_{i+1}| &\leq  \frac{32 \log n}{\delta} \sum_{X \in \hat{V}_{i}}  \lg (n  - |X \cap S_{i}|) |X \cap S_{i}| &  \text{for }i \geq 0
\end{align}

We prove by induction on $i$. It is easy to see that $S_0$ has cardinality $n$ since we initialize it to the node set in procedure <ref>, and since each set $S_i$ is an increasing set over time.

Let us therefore focus on $i > 0$. Let us first assume that the separator nodes were added by the procedure $\textsc{OutSep}(\cdot)$ (analogously $\textsc{InSep}(\cdot)$). Since the procedure is invoked on an induced subgraph $\hat{G}_i[X]$ that was formerly strongly-connected, we have that either $V_{Sep}$ or $X \setminus (V_{Sep} \;\cup\; S_{Sep})$ (or both) contain at most half the $S_i$-nodes originally in $X$. Let $Y$ be such a side. Since adding $S_{Sep}$ to $S_i$ separates the two sides, we have that RHS of the equation is increased by at least $\frac{32 \log n}{\delta} |Y \cap S_i|$ since $\lg( n - |Y \cap S_i|) |Y \cap S_i| - \lg( n - |X \cap S_i|) |Y \cap S_i| \geq |Y \cap S_i|$. Since we increase the LHS by at most $\frac{4 \log n}{\delta} |Y \cap S_i|$ by the guarantees in Lemma <ref>, the inequality is still holds.

Otherwise, separator nodes were added due to procedure $\textsc{Split}(\cdot)$. But then we can straight-forwardly apply Lemma <ref> which immediately implies that the inequality still holds.

Finally, the hierarchy might augment the set $S_i$ in line <ref>, but we observe that $f(s) = \lg(n - s) * s$ is a function increasing in $s$ for $s \leq \frac{1}{2} n$ which can be proven by finding the derivative. Thus adding nodes to the set $S_i$ can only increase the RHS whilst the LHS remains unchanged.

During the entire course of deletions, we have, for any $i \geq 0$,
\[
|S_{i+1}| \leq \frac{32 \lg^2 n}{\delta} |S_{i}|.
\]

§ PUTTING IT ALL TOGETHER

By Corollary <ref>, using $\delta = 64 \lg^2 n$, we enforce that each $|S_i| \leq n/2^i$, so $\hat{G}_{\lfloor \lg{n} \rfloor + 1}$ is indeed the condensation of $G$. Thus, we can return on queries asking whether $u$ and $v$ are in the same SCC of $G$, simply by checking whether they are represented by the same node in $\hat{G}_{\lfloor \lg{n} \rfloor + 1}$ which can be done in constant time.

By Lemma <ref>, we have that with probability $\frac{2}{3}$, that every time a node leaves a GES, its induced subgraph contains at most a fraction of $\frac{2}{3}$ of the underlying vertices of the initial graph. Thus, in expectation each vertex in $V$ participates on each level in $O(\log n)$ GES-trees. Each time it contributes to the GES-trees running time by its degree times the depth of the GES-tree which we fixed to be $\delta$. Thus we have expected time $O(\sum_{v \in V} \mathbf{deg}(v) \delta \log n) = O(m \log^3 n)$ to maintain all the GES-trees on a single level by Lemma <ref>. There are $O(\log n)$ levels in the hierarchy, so the total expected running time is bounded by $O(m \log^4 n)$.

By Lemmas <ref>, the running time for invoking $\textsc{Split}(G[X], S, \delta/2)$ can be bounded by $O(E(X) \delta \log n) = O(E(X) \log^3 n)$. After we invoke  $\textsc{Split}(G[X], S, \delta/2)$ in algorithm <ref>, we expect with constant probability again by Lemma <ref>, that each vertex is at most $O(\log n)$ times in an SCC on which the $\textsc{Split}(\cdot)$ procedure is invoked upon. We therefore conclude that total expected running time per level is $O(m \log^4 n)$, and the overall total is $O(m \log^5 n)$.

Finally, we can bound the total running time incurred by all invocations of $\textsc{InSep}(\cdot)$ and $\textsc{OutSep}(\cdot)$ outside of $\textsc{Split}(\cdot)$ by the same argument and obtain total running time $O(m \log^2 n)$ since each invocation takes time $O(E(G))$ on a graph $G$.

This completes the running time analysis, establishing the total expected running time $O(m \log^5 n)$ which concludes our proof of Theorem <ref>.

CHAPTER: A RANDOMIZED ALGORITHM FOR DECREMENTAL SSSP IN DENSE DIGRAPHS

In this chapter, we prove the first part of <Ref>. We state the precise Theorem that we prove below.

Given a decremental input graph $G=(V,E,w)$ with $n = |V|, m=|E|$ and aspect ratio $W$, a dedicated source $r \in V$ and $\epsilon > 0$, there is a randomized algorithm that maintains a distance estimate $\widetilde{\mathbf{dist}}(r,x)$, for every $x \in V$, such that

\[
{\mathbf{dist}}_G(r,x) \leq \widetilde{\mathbf{dist}}(r,x) \leq (1+\epsilon) {\mathbf{dist}}_G(r,x)
\]

at any stage w.h.p. The algorithm has total expected update time $\tilde{O}(n^2 \log^4 W/\poly(\epsilon))$. Distance queries are answered in $O(1)$ time, and a corresponding path $P$ can be returned in $O(|P|)$ time. The algorithm works against a non-adaptive adversary.

We start this chapter by introducing some additional preliminaries that are specific to this chapter. We then give an extended overview of our data structure, and finally provide formal proofs (however, we only sketch some of the more technical proofs).

§ ADDITIONAL PRELIMINARIES

Exponential Distribution. Finally, we make use of the exponential distribution, that is we use random variables $X$ with cumulative distribution function $F_X(x,\lambda) = 1 - e^{-\lambda x}$ for all $x \geq 0, \lambda > 0$, which we denote by the shorthand $X \sim \textsc{Exp}(\lambda)$. If $X \sim \textsc{Exp}(\lambda)$ is clear, we also use $F_X(x)$ in place of $F_X(x,\lambda)$. The exponential distribution has the special property of being memoryless, that is if $X \sim \textsc{Exp}(\lambda)$, then

\[
\mathbb{P}[X > s + t \;|\; X > t] = \mathbb{P}[X > s].
\]

Generalized Topological Order. We define a generalized topological order
$\textsc{GeneralizedTopOrder}(H)$ to be a tuple $(\mathcal{V}, \tau)$ where $\mathcal{V}$ is the set of SCCs of $H$ and $\tau : \mathcal{V} \rightarrow [0,n)$ is a function that maps any sets $X, Y \in \mathcal{V}$ such that $\tau(X) < \tau(Y)$, if $X \leadsto_H Y$ and such that $[\tau(X), \tau(X) + |X|) \cap [\tau(Y), \tau(Y) + |Y|) = \emptyset$. Thus, $\tau$ effectively establishes a one-to-one correspondence between $|X|$-sized intervals and SCCs $X$ in $H$. We point out that a $\textsc{GeneralizedTopOrder}(H)$ can always be computed in $O(|E(H)|)$ time <cit.>. In fact, a generalized topological order can also be maintained efficiently in a decremental graph $H$. Here, we say that $(\mathcal{V},\tau)$ is a dynamic tuple that forms a generalized topological order of $H$ if it is a topological order for all versions of $H$. Further, we say that $(\mathcal{V}, \tau)$ has the nesting property, if for any set $X \in \mathcal{V}$ and a set $Y \supseteq X$ that was in $\mathcal{V}$ at an earlier stage, we have $\tau(X) \in [\tau(Y), \tau(Y) + |Y| - |X|]$; in other words, the interval $[\tau(X), \tau(X)+|X|)$ is entirely contained in the interval $[\tau(Y), \tau(Y) + |Y|)$. Thus, the associated interval with $X$ is contained in the interval associated with $Y$. We refer to the following result that can be obtained straight-forwardly by combining the data structure given in <Ref> and the static procedure by Tarjan <cit.> as described in <cit.>.

Given a decremental digraph $H$, there exists an algorithm that can maintain the generalized topological order $(\mathcal{V}, \tau)$ of $H$ where $\tau$ has the nesting property. The algorithm runs in expected total update time $O(m \log^4 n)$, is randomized and works against an adaptive adversary.

§ OVERVIEW

We now give an overview of our algorithm. In order to illustrate the main concepts, we start by giving a simple algorithm to obtain total update time $O(n^2 \log n/\epsilon)$ in directed acyclic graphs (DAGs). While this algorithm was previously not explicitly mentioned, it follows rather directly from the techniques developed in <cit.>. We present this algorithm to provide intuition for our approach and motivates our novel notion of approximate topological orders. In the light of approximate topological orders, we then shed light on limitations of the previous approach in <cit.> and present techniques to surpass these limitations to obtain <Ref>. In this overview, we focus on obtaining an SSSP algorithm that runs in $\tilde{O}(n^2 \log^4 W / \poly( \epsilon))$ expected update time.

§.§ A Fast Algorithm for DAGs

The Topological Order Difference. Let $G = (V,E,w)$ be a DAG and let $\tau$ be the function returned by  $\textsc{GeneralizedTopOrder}(G)$ computed on the initial version of $G$ (since $G$ is a DAG, this is just a standard topological order). Let us now make an almost trivial observation: for any shortest $s$-to-$t$ path $\pi_{s,t}$, in any version of $G$, the sum of topological order differences is bounded by $n$. More formally:

\begin{equation}
\label{eq:defT}
\mathcal{T}(\pi_{s,t}, \tau) \stackrel{\text{def}}{=} \sum_{(u,v) \in \pi_{s,t}} \tau(v) - \tau(u) = \tau(t) - \tau(s) \leq n.
\end{equation}

Observe that every path in $G$ can only contain few edges $(u,v)$ with large topological order difference, i.e. with $\tau(v) - \tau(u)$ large, by the pigeonhole principle.

Reviewing the ES-tree. To understand how this fact can be exploited, recall that in the classic ES-tree algorithm (see <Ref>), a vertex $v$ that currently does not have an in-edge in the tree $T$, searches its in-neighborhood $\mathcal{N}_{in}(v$ for a vertex $x$ such that

\begin{equation}
\label{eq:enforce2}
\widetilde{\mathbf{dist}}(r,x)+ w(x,v) \leq \widetilde{\mathbf{dist}}(r,v).
\end{equation}

Only if no such $x$ exists, then $\widetilde{\mathbf{dist}}(r,v)$ has to be incremented. However, observe that if a vertex $v$ was only allowed to scan a certain vertex $x \in \mathcal{N}^{in}(v)$ after every $i$ distance estimate increments (for example whenever $\widetilde{\mathbf{dist}}(r,v) $ is divisible by $i$) then this corresponds to enforcing that at all times $\widetilde{\mathbf{dist}}(r,x)+ w(x,v) + i - 1 \leq \widetilde{\mathbf{dist}}(r,v)$ since we check equation <ref> every $i$ steps (in particular, for $i=1$, we get an exact algorithm). Consequently, we get at most $i-1$ additive error in the distance estimate for any $t$ whose shortest $r$-to-$t$ path $\pi_{r,t}$ contains $(x,v)$. On the other hand, we only need to scan and check the edge $(x,v)$, by the classic runtime analysis argument, $\delta / i$ times instead of $\delta$ times[This trade-off was first observed in <cit.>.].

Improving the Running Time. Let us now exploit Inequality <ref>. We therefore define

\[
B_j(v) = \{ u \in \mathcal{N}^{in}(v) \textit{ with }  2^{j} \leq \tau(v) - \tau(u) < 2^{j+1}\}
\]

for every $v \in V$ and $0 \leq j \leq \lg n$; the $B_j(v)$ partition the in-neighborhood of $v$ according to topological order difference to $v$. Observe that $|B_j(v)| \leq 2^j$. Now, consider the algorithm as above where for every vertex $v$, instead of checking all $\mathcal{N}^{in}(v)$, we only check edge $(x,v)$ for $x \in B_j(v)$ if
$\widetilde{\mathbf{dist}}(r,v)$ is divisible by $\lceil2^j\frac{\epsilon \delta}{n}\rceil$.
By the arguments above the total running time now sums to

\[O\left(\sum_{v \in V} \sum_{0 \leq j \leq \lg n} |B_j(v)| \frac{\delta}{2^j\frac{\epsilon \delta}{n}}\right) = O\left(\sum_{v \in V} \sum_{0 \leq j \leq \lg n} 2^{j+2} \frac{\delta}{2^j\frac{\epsilon \delta}{n}}\right) = \tilde{O}(n^2/\epsilon).
\]

Bounding the Error. Fix a shortest $r$-to-$t$ path $\pi_{r,t}$, and consider any edge $(u,v) \in \pi_{r,t}$ with $u \in B_{j+1}(v)$. We observe that the edge $(u,v)$ contributes at most an additive error of $2^{j+1}\frac{\epsilon \delta}{n}$ to $\widetilde{\mathbf{dist}}(r,t)$ since it is scanned every $\lceil 2^{j}\frac{\epsilon \delta}{n} \rceil$ distance values and if $\lceil 2^{j}\frac{\epsilon \delta}{n} \rceil$ is equal to $1$ it does not induce any error.