Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs

Zhao, Yibin

doi:10.4230/LIPIcs.ICALP.2026.157

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs

Yibin Zhao

University of Toronto, Canada

Abstract

Recent years have seen extensive research on directed graph sparsification. In this work, we initiate the study of fast fully dynamic spectral and cut sparsification algorithms for directed graphs.

We introduce a new notion of spectral sparsification called degree-balance preserving spectral approximation, which maintains the difference between the in-degree and out-degree of each vertex. The approximation error is measured with respect to the corresponding undirected Laplacian. This notion is equivalent to direct Eulerian spectral approximation when the input graph is Eulerian. Our algorithm achieves an amortized update time of $O(\varepsilon^{-2}\cdot\text{polylog}(n))$ and produces a sparsifier of size $O(\varepsilon^{-2}n\cdot\text{polylog}(n))$ . Additionally, we present an algorithm that maintains a constant-factor approximation sparsifier of size $O(n\cdot\text{polylog}(n))$ against an adaptive adversary for $O(\text{polylog}(n))$ -partially symmetrized graphs, a notion introduced in [Kyng-Meierhans-Probst Gutenberg ’22]. A $\beta$ -partial symmetrization of a directed graph $\vec{G}$ is the union of $\vec{G}$ and $\beta\cdot G$ , where $G$ is the corresponding undirected graph of $\vec{G}$ . This algorithm also achieves a polylogarithmic amortized update time.

Moreover, we develop a fully dynamic algorithm for maintaining a cut sparsifier for $\beta$ -balanced directed graphs, where the ratio between weighted incoming and outgoing edges of any cut is at most $\beta$ . This algorithm explicitly maintains a cut sparsifier of size $O(\varepsilon^{-2}\beta n\cdot\text{polylog}(n))$ in worst-case update time $O(\varepsilon^{-2}\beta\cdot\text{polylog}(n))$ .

Keywords and phrases:

Dynamic graph algorithm, Spectral graph theory, Sparsifier

Category:

Track A: Algorithms, Complexity and Games

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Dynamic graph algorithms ; Theory of computation

\rightarrow

Sparsification and spanners

Related Version:

Full Version: https://arxiv.org/abs/2507.19632 [48]

Acknowledgements:

The author would like to thank Sushant Sachdeva and Richard Peng for helpful discussions.

DOI:

10.4230/LIPIcs.ICALP.2026.157

Event:

53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Designing spectral algorithms for directed graphs is a major frontier in algorithmic spectral graph theory. These algorithms have found numerous applications, ranging from fast algorithms for processing Markov chains [21, 3] to deterministic low-space computation [4]. Spectral sparsification of directed (Eulerian) graphs has emerged as a central topic in this area, with considerable recent advances [20, 16, 5, 44, 32, 38]. In particular, faster spectral sparsification algorithms that produce sparser directed Eulerian sparsifiers directly lead to faster computation of approximate Personalized PageRank vectors [21], stationary distributions, hitting times, escape probabilities of random walks [21], and approximate Perron vectors [3] through efficient directed Eulerian Laplacian solvers [20, 42].

In this work, we initiate the study of spectral and cut sparsification for dynamically changing directed graphs. We believe that our dynamic algorithms will serve as the foundation for efficient dynamic computations of the aforementioned problems.

Unlike undirected spectral sparsification, developing a useful notion of directed spectral or cut sparsification has been particularly challenging. Consider the complete directed bipartite graph where every node on one side of the bipartition has a directed edge to every node on the other side. Any sparsifier that approximately preserves all directed cuts in such a graph cannot delete any edges. For cut sparsification, Cen, Cheng, Panigrahi, and Sun [13] restricted the sparsification guarantees to only apply to cuts with values close to their corresponding cuts in the reverse direction.

Definition 1 ( $\beta$ -balanced directed cut approximation).

$\vec{H}=(V,E_{\vec{H}},\boldsymbol{\mathrm{w}}_{\vec{H}})$ is a $(\beta,\varepsilon)$ -balanced directed cut approximation of $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ if for all non-trivial cuts $(U,V\setminus U)$ satisfying $\frac{1}{\beta}\boldsymbol{\mathrm{w}}(V\setminus U,U)\leq\boldsymbol{\mathrm{% w}}(U,V\setminus U)\leq\beta\boldsymbol{\mathrm{w}}(V\setminus U,U)$ , $\vec{H}$ satisfies that

(1-\varepsilon)\boldsymbol{\mathrm{w}}(U,V\setminus U)\leq\boldsymbol{\mathrm{% w}}_{\vec{H}}(U,V\setminus U)\leq(1+\varepsilon)\boldsymbol{\mathrm{w}}(U,V% \setminus U).

This notion of $\beta$ -balanced cut sparsification is motivated by applications in solving flows and cuts problems [24, 34], as the residual graphs that appear in the intermediate steps of the maxflow algorithms are naturally balanced. These sparsifiers have found further application in recent work by Goranci, Henzinger, Räcke, and Sricharan [29], who used them to achieve the first dynamic incremental maxflow algorithm with polylogarithmic amortized update time for dense graphs ( $m=\Omega(n^{2})$ ).

Cohen, Kelner, Peebles, Peng, Rao, Sidford, and Vladu [20] addressed the directed spectral sparsification problem by focusing on directed Eulerian graphs (where every vertex has equal weighted in-degree and out-degree). This requirement might seem overly restrictive, since all directed cuts of an Eulerian graph must have a balance factor $\beta=1$ . However, Cohen et al. demonstrated that their sparsification approach suffices for developing fast solvers for all directed Laplacian linear systems (even those not corresponding to an Eulerian graph). In this paper, we propose a relaxed notion of directed spectral approximation closely related to that of [20], where the sparsifier only needs to maintain the degree balances.

Definition 2 (Degree balance preserving directed spectral approximation).

$\vec{H}=(V,E_{\vec{H}},\boldsymbol{\mathrm{w}}_{\vec{H}})$ is a $\varepsilon$ -degree balance preserving directed spectral approximation of $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ if for the corresponding undirected $G\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{G})$ ,

\forall\boldsymbol{\mathrm{x}},\boldsymbol{\mathrm{y}}\in\mathbb{R}^{V},\quad% \left|\boldsymbol{\mathrm{x}}^{\top}(\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}}% -\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{H}})\boldsymbol{\mathrm{y}}\right|\leq% \varepsilon\sqrt{\boldsymbol{\mathrm{x}}^{\top}\boldsymbol{\mathrm{{L}}}_{G}% \boldsymbol{\mathrm{x}}\cdot\boldsymbol{\mathrm{y}}^{\top}\boldsymbol{\mathrm{% {L}}}_{G}\boldsymbol{\mathrm{y}}}.

(1)

This definition of directed spectral approximation has been implicitly used in almost all previous works in the directed Laplacian literature (e.g. [20, 19, 16, 37, 44, 32]). We note that the degree balance preserving requirement is implicitly ensured by (1): if the degree balance is not preserved, then there are some vectors $\boldsymbol{\mathrm{x}},\boldsymbol{\mathrm{y}}$ such that the left hand side of (1) is non-zero while the right hand side is zero (see Lemma 10). The relaxation to any directed graph is necessary for dynamically changing graphs, as modifying from one directed Eulerian graph to another requires at least 3 individual edge updates. Whenever a dynamic directed graph $\vec{G}$ becomes Eulerian, our degree balance preservation requirement naturally ensures that the dynamically maintained sparsifier is also Eulerian.

For both directed balanced cut sparsification and degree balance preserving spectral sparsification, we ask the natural question of whether a fully dynamic algorithm with polylogarithmic update time exists for maintaining a nearly-linear size sparsifier (i.e., the number of edges in the sparsifier is at most $O(n\cdot\textup{poly}(\varepsilon^{-1},\log n)$ ) for directed graphs. Previous work by Abraham, Durfee, Koutis, Krinninger, and Peng [1] established the existence of such dynamic algorithms for undirected graphs. In this work, we answer this question affirmatively for the directed case.

1.1 Our results

Our first result is a fully dynamic algorithm for degree balance preserving directed spectral sparsification with polylogarithmic amortized update time.

Theorem 3 (Explicit dynamic directed spectral sparsifier).

Given a directed graph $\vec{G}$ on vertices $V$ and with polynomially bounded edge weights, we can maintain explicitly a graph $\vec{H}$ on vertices $V\cup X$ such that the Schur complement $\operatorname{\mathtt{Sc}}(\vec{H},V)$ onto the original vertices is a $\varepsilon$ -degree balance preserving directed sparsifier. $\vec{H}$ has size $\widetilde{O}(\varepsilon^{-2}n)$ ¹¹1We use $\widetilde{O}(\cdot)$ to hide polylogarithmic factors in $n$ . and satisfies $|X|=\widetilde{O}(n)$ . The algorithm has amortized recourse and update time $\widetilde{O}(\varepsilon^{-2})$ per edge insertion or deletion and works against an oblivious adversary.

Our algorithm explicitly maintains a sparsifier at the expense of $\widetilde{O}(n)$ extra vertices. We demonstrate in Lemma 13 (Section 3) that these extra vertices do not affect the usefulness of our theorem. Crucially, having an explicit sparsifier with low recourse enables further dynamic algorithms using our algorithm as a dynamic subroutine. A version of this theorem that exactly preserves both in-degrees and out-degrees is presented in Theorem 24. We also present two different algorithms that maintain implicit sparsifiers on the original set of vertices in the full version.

As observed by [11] for dynamic undirected spectral sparsifiers, dynamic algorithms that maintain implicit sparsifiers already support important applications. For example, one can maintain a dynamic row and column diagonally dominant (RCDD) Z-matrix²²2A RCDD matrix is a real M-matrix with non-negative row and column sums. solver through a reduction to directed Eulerian spectral sparsifier by [21] and by running a non-iterative static directed Eulerian Laplacian solver (e.g., [42]) on top of the sparsifier.

Corollary 4 (Dynamic RCDD Z-matrix solver).

Given a dynamic RCDD Z-matrix $\boldsymbol{\mathrm{{M}}}$ of dimension $n$ and $\varepsilon\in(0,1)$ , we can maintain a data structure in $\widetilde{O}(\varepsilon^{-2}n)$ amortized update time which supports solving the linear system $\boldsymbol{\mathrm{{M}}}\boldsymbol{\mathrm{x}}=\boldsymbol{\mathrm{b}}$ for any $\boldsymbol{\mathrm{b}}\in\mathbb{R}^{n}$ to $\varepsilon$ -approximation in time $\widetilde{O}(\varepsilon^{-2}n)$ .

Our next result, parallel to spectral sparsification, is a simple fully dynamic balanced directed cut sparsification algorithm with polylogarithmic worst-case update time.

Theorem 5 (Dynamic $\beta$ -balanced cut sparsifier).

Given a directed graph with polynomially bounded edge weights, we can maintain explicitly a $(\beta,\varepsilon)$ -balanced directed cut sparsifier of size $\widetilde{O}(\varepsilon^{-2}\beta n)$ with worst-case update time $\widetilde{O}(\varepsilon^{-2}\beta)$ per edge insertion or deletion against an oblivious adversary.

Unlike spectral sparsification, cut sparsification does not require degree fixing. As a result, our data structure can maintain a cut sparsifier explicitly without extra vertices. Additionally, we present an algorithm with improved amortized recourse and update time (see Theorem 27 in Section 4). In achieving Theorem 5, we also prove that independent edge sampling based on inverse undirected edge connectivity is sufficient for balanced directed cut approximation.

Theorem 6 (Improved static $\beta$ -balanced cut sparsifier).

There is a sparsification algorithm that, given a weighted directed graph and the edge connectivities of its corresponding undirected graph, computes a $(\beta,\varepsilon)$ -balanced directed cut sparsifier with $O(\varepsilon^{-2}\beta n\log n)$ edges in linear time.

Finally, we present a fully dynamic directed spectral sparsification algorithm that works against an adaptive adversary. This result requires more detailed explanation, which we provide below.

We first remind readers that our degree balance preserving sparsifier requires the approximation factor $\varepsilon<1$ . This requirement is necessary and warranted – for any directed Eulerian graph, an empty graph on the same set of vertices can serve as a constant good approximation. To the best of our knowledge, there exists no notion of directed spectral approximation that extends beyond constant approximation. This limitation is particularly problematic since the state-of-the-art adaptive undirected cut and spectral sparsifier from [11] require the multiplicative approximation factor to be at least $O(\log n)$ .

Kyng, Meierhans, and Probst Gutenberg [37] circumvented this issue by considering the sparsification problem on a related graph called a partial symmetrization. Specifically, a $\beta$ -partial symmetrization of a directed graph $\vec{G}$ is defined by $\vec{G}^{(\beta)}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\beta\cdot G% \cup\vec{G}$ , which combines the directed graph with a copy of its corresponding undirected graph $G\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{G})$ scaled by a factor of $\beta$ . They showed that a partially symmetrized Eulerian graph serves as a good approximate pseudoinverse of the original directed graph (see Lemma 37).

Definition 7 (Approximate pseudoinverse, [21]).

For $\varepsilon\geq 0$ , a square matrix $\boldsymbol{\mathrm{{Z}}}$ is an $\varepsilon$ -approximate pseudoinverse of square matrix $\boldsymbol{\mathrm{{M}}}$ with respect to a Hermitian PSD matrix $\boldsymbol{\mathrm{{U}}}$ if $\ker(\boldsymbol{\mathrm{{U}}})\subseteq\ker(\boldsymbol{\mathrm{{M}}})=\ker(% \boldsymbol{\mathrm{{M}}}^{\top})=\ker(\boldsymbol{\mathrm{{Z}}})=\ker(% \boldsymbol{\mathrm{{Z}}}^{\top})$ , and

\left\lVert\boldsymbol{\mathrm{{P}}}_{\textup{im}(\boldsymbol{\mathrm{{M}}})}-% \boldsymbol{\mathrm{{Z}}}\boldsymbol{\mathrm{{M}}}\right\rVert_{\boldsymbol{% \mathrm{{U}}}\to\boldsymbol{\mathrm{{U}}}}\leq\varepsilon,

where $\boldsymbol{\mathrm{{P}}}_{\textup{im}(\boldsymbol{\mathrm{{M}}})}$ is the identity matrix on the image of $\boldsymbol{\mathrm{{M}}}$ .

Moreover, when $\beta$ is large, the directed portion of $\vec{G}^{(\beta)}$ can be sparsified much more aggressively under the notion of degree balance preserving spectral approximation, since

\left\lVert\boldsymbol{\mathrm{{L}}}_{G^{(\beta)}}^{\frac{{\dagger}}{2}}(\vec{% \boldsymbol{\mathrm{{L}}}}_{\vec{G}}-\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{H}}% )\boldsymbol{\mathrm{{L}}}_{G^{(\beta)}}^{\frac{{\dagger}}{2}}\right\rVert_{% \textup{op}}=\frac{1}{2\beta+1}\left\lVert\boldsymbol{\mathrm{{L}}}_{G}^{\frac% {{\dagger}}{2}}(\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}}-\vec{\boldsymbol{% \mathrm{{L}}}}_{\vec{H}})\boldsymbol{\mathrm{{L}}}_{G}^{\frac{{\dagger}}{2}}% \right\rVert_{\textup{op}}.

Further sparsification can also be performed on the undirected portion of the graph $\vec{G}^{(\beta)}$ to ultimately produce a sparse approximation. These layers of approximation allow them to build a sparse preconditioner chain, which can be applied to solve directed Eulerian Laplacian systems using iterative solvers. See Section 5 for more details. Our dynamic algorithm efficiently maintains these sparsification layers under adaptive edge insertions and deletions.

Theorem 8 (Adaptive directed spectral sparsification quadruple).

Given a directed graph $\vec{G}$ on vertices $V$ and with polynomially bounded edge weights, we can maintain explicitly a set of 3 directed graphs $\vec{G}_{1}=\vec{G}^{(\beta)},\vec{G}_{2}^{\prime},\vec{G}_{3}^{\prime}$ with $\vec{G}_{0}=\vec{G}$ and $V(\vec{G}_{2}^{\prime})=V\cup X$ and $V(\vec{G}_{3}^{\prime})=V\cup X\cup Y$ . For $\vec{G}_{2}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\operatorname{% \mathtt{Sc}}(\vec{G}_{2}^{\prime},V)$ and $\vec{G}_{3}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\operatorname{% \mathtt{Sc}}(\vec{G}_{3}^{\prime},V)$ , they satisfy that

1.

when $\vec{G}$ is Eulerian $\vec{G}_{i}$ is a $1-\frac{1}{\textup{polylog}(n)}$ -approximate pseudoinverse of $\vec{G}_{i-1}$ for all $i=1,2,3$ and degree balance preserving with respect to $\vec{G}$ ,
2.

$\vec{G}_{3}^{\prime}$ has size $\widetilde{O}(n)$ and $\vec{G}_{2}^{\prime}$ has size $O(m)$ .

The algorithm works against an adaptive adversary, has preprocessing time $\widetilde{O}(m)$ and amortized update time $\widetilde{O}(1)$ .

In this paper, we provide an overview of our algorithms and techniques. We refer readers to the full version of our paper for formal statements and detailed proofs.

1.2 Related works

Static directed graph sparsification

The notion of Eulerian Laplacian spectral sparsification was introduced by [20] to construct fast directed Eulerian Laplacian linear system solvers. These solvers have applications in various computational problems related to random walks on general directed graphs, through reductions given in [21, 3]. Cohen et al. [20] gave the first $\widetilde{O}(m)$ time algorithm for constructing Eulerian sparsifiers with $\widetilde{O}(\varepsilon^{-2}n)$ edges, based on expander decompositions.

As an alternative approach, Chu et al. [16] introduced the short cycle decomposition technique and used it to give a polynomial-time algorithm for computing sparsifiers with significantly improved sparsity. This approach was subsequently improved by the work of [40, 41, 44]. Notably, [44] also demonstrated an improved existential result on the sparsity of Eulerian sparsifiers by leveraging techniques from matrix discrepancy theory [7]. This discrepancy approach was earlier introduced by Jambulapti, Reis, and Tian [31] for constructing undirected degree preserving spectral sparsifiers with optimal sparsity in almost linear time.

Recently, Jambulapati et al. [32] achieved state-of-the-art Eulerian sparsification results for both efficient sparsification and existential sparsity using a combination of techniques: effective resistance decomposition and sampling by electrical circulations. When combined with the reduction by Peng and Song [42], they provided the state-of-the-art Eulerian Laplacian solver that runs in $\breve{O}(m\log^{3}n+n\log^{6}n)$ time ³³3We use $\breve{O}(\cdot)$ to hide polyloglog factors in $n$ .. Lau, Wang, and Zhou [38] gave a derandomized Eulerian sparsification algorithm using the “deterministic discrepancy walk” approach from [43]. They extended their sparsification result to satisfy a stronger notion of directed spectral approximation known as “singular value (SV) approximation” [5].

For directed cut sparsification, the notion of balanced cut approximation was introduced by Cen et al. [13] for sparsification of directed graphs where each cut has approximately the same weight as the cut in the reverse direction. Efficient cut sparsification algorithms have applications in minimum cut approximations for such balanced graphs [24]. Cen et al. designed an algorithm for constructing cut sparsifiers with $O(\varepsilon^{-2}\beta n\log n)$ edges for balance factor $\beta$ by sampling using the inverse undirected edge strength, introduced in [9] for undirected cut sparsification. This upper bound was later proven to be nearly tight by Chen et al. [15], who gave a bit complexity lower bound of $\Omega(\varepsilon^{-2}\beta n)$ . Theorem 6 complements the results of [13] by showing that sampling with probability inversely proportional to undirected edge connectivities, similar to [27] for undirected cut sparsification, achieves the same sparsity guarantee.

Recently, Goranci, Henzinger, Räcke, and Sricharan [29] independently discovered a similar generalization to balanced cut approximation using the framework of [27]. They proved a stronger result showing that any undirected edge connectivity measure is suitable for sparsification of balanced directed cuts. One key difference is that their general result has a slightly worse sparsity guarantee compared to ours that specifically uses undirected edge connectivity. Their sparsification algorithm works in conjunction with a dynamic NI index algorithm to dynamically sparsify residual networks in incremental maxflow problems.

Dynamic graph sparsification

Dynamic graph sparsification problems have been studied extensively for undirected graphs. There is a long line of work [6, 23, 8, 25, 10, 11, 14, 47, 18] on maintaining spanners – graph sparsifiers that approximately preserve distances – with various assumptions about updates (amortized or worst-case) and adversaries (oblivious or adaptive).

Abraham, Durfee, Koutis, Krinninger, and Peng [1] initiated the study of dynamic undirected spectral and cut sparsifications. They developed fully dynamic spectral sparsifiers with $\widetilde{O}(\varepsilon^{-2}n)$ edges and $\widetilde{O}(\varepsilon^{-2})$ amortized update time against oblivious adversaries by adapting the static spectral sparsification algorithm of Koutis and Xu [36]. Their algorithm maintains a bundle of dynamic spanners [8] that can certify edges with small effective resistances, the central value for undirected spectral sparsification. By swapping spanners with a bundle of dynamic (approximate) maximum spanning forests [30, 33, 28] that could certify edge connectivities, they also showed fully dynamic algorithms for cut sparsification with worst-case update time of $\widetilde{O}(\varepsilon^{-2})$ against an oblivious adversary.

These results were subsequently strengthened by Bernstein, van den Brand, Probst Gutenberg, Nanongkai, Saranurak, Sidford, and Sun [11] to either work against adaptive adversaries or have worst-case update time guarantees. At the core of these results is a black-box reduction that reduces fully dynamic sparsification problems to decremental sparsification problems on almost uniform degree expanders. A version of their framework serves as the basis of our dynamic algorithms. To handle probabilistic dependencies introduced by adaptive adversaries, Bernstein et al. developed a technique called proactive sampling, where an edge update incurs multiple re-samplings with increasing intervals. One downside is that their adaptive algorithms have a significant trade-off between update time and approximation factor, leading to at least polylogarithmic approximations for any subpolynomial update time.

2 Preliminaries

All $\log$ are base $2$ unless otherwise specified. We denote $\log_{e}$ by $\ln$ . When discussing a graph clear from context with $n$ vertices and edge weight ratio bounded by $W$ . We use the $\breve{O}$ notation to hide $\textup{polyloglog}(nW)$ factors for brevity (in runtimes only). We let $[n]\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\{i\in\mathbb{N}\mid 1\leq i% \leq n\}$ .

Vectors and Matrices

Vectors are denoted in lower-case boldface. $\boldsymbol{\mathrm{0}}_{d}$ and $\boldsymbol{\mathrm{1}}_{d}$ are the all-zeroes and all-ones vector respectively of dimension $d$ . $\boldsymbol{\mathrm{e}}_{i}$ denotes the $i^{\text{th}}$ basis vector. $\boldsymbol{\mathrm{u}}\circ\boldsymbol{\mathrm{v}}$ denotes the entrywise product of $\boldsymbol{\mathrm{u}},\boldsymbol{\mathrm{v}}$ of equal dimension.

Matrices are denoted in upper-case boldface. We refer to the $i^{\text{th}}$ row and $j^{\text{th}}$ column of matrix $\boldsymbol{\mathrm{{M}}}$ by $\boldsymbol{\mathrm{{M}}}_{i:}$ and $\boldsymbol{\mathrm{{M}}}_{:j}$ respectively. We use $[\boldsymbol{\mathrm{v}}]_{i}$ to index into the $i^{\text{th}}$ coordinate of vector $\boldsymbol{\mathrm{v}}$ , and let $[\boldsymbol{\mathrm{{M}}}]_{i:}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=% }}\boldsymbol{\mathrm{{M}}}_{i:}$ , $[\boldsymbol{\mathrm{{M}}}]_{:j}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=% }}\boldsymbol{\mathrm{{M}}}_{:j}$ , and $[\boldsymbol{\mathrm{{M}}}]_{ij}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=% }}\boldsymbol{\mathrm{{M}}}_{ij}$ in contexts where $\boldsymbol{\mathrm{v}}$ , $\boldsymbol{\mathrm{{M}}}$ have subscripts.

$\mathbf{I}_{d}$ is the $d\times d$ identity matrix. For $\boldsymbol{\mathrm{v}}\in\mathbb{R}^{d}$ , $\textbf{{diag}}\left(\boldsymbol{\mathrm{v}}\right)$ denotes the associated diagonal $d\times d$ matrix. For linear subspace $S$ of $\mathbb{R}^{d}$ , $\dim(S)$ is its dimension and $\boldsymbol{\mathrm{{P}}}_{S}$ is the orthogonal projection matrix onto $S$ . We let $\ker(\boldsymbol{\mathrm{{M}}})$ , $\textup{im}(\boldsymbol{\mathrm{{M}}})$ , and $\boldsymbol{\mathrm{{M}}}^{\dagger}$ denote the kernel, image and pseudoinverse of $\boldsymbol{\mathrm{{M}}}$ . We denote the operator norm (largest singular value) of matrix $\boldsymbol{\mathrm{{M}}}$ by $\left\lVert\boldsymbol{\mathrm{{M}}}\right\rVert_{\textup{op}}$ . The number of nonzero entries of a matrix $\boldsymbol{\mathrm{{M}}}$ (resp. vector $\boldsymbol{\mathrm{v}}$ ) is denoted $\textup{nnz}(\boldsymbol{\mathrm{{M}}})$ (resp. $\textup{nnz}(\boldsymbol{\mathrm{v}})$ ), and the subset of indices with nonzero entries is $\textup{supp}(\boldsymbol{\mathrm{{M}}})$ (resp. $\textup{supp}(\boldsymbol{\mathrm{v}})$ ).

We use $\preceq$ to denote the Loewner partial order on $\mathbb{S}^{d}$ , the symmetric $d\times d$ matrices. For $\boldsymbol{\mathrm{{M}}}\in\mathbb{S}^{d}$ and $i\in[d]$ , we let $\lambda_{i}(\boldsymbol{\mathrm{{M}}})$ denote the $i^{\text{th}}$ smallest eigenvalue of $\boldsymbol{\mathrm{{M}}}$ , so $\lambda_{1}(\boldsymbol{\mathrm{{M}}})\leq\lambda_{2}(\boldsymbol{\mathrm{{M}}% })\leq\ldots\leq\lambda_{d}(\boldsymbol{\mathrm{{M}}})$ . For positive semidefinite $\boldsymbol{\mathrm{{A}}}\in\mathbb{S}^{d}$ , we define the seminorm induced by $\boldsymbol{\mathrm{{A}}}$ by $\|\boldsymbol{\mathrm{x}}\|_{\boldsymbol{\mathrm{{A}}}}^{2}\stackrel{{% \scriptstyle\textup{\tiny def}}}{{=}}\boldsymbol{\mathrm{x}}^{\top}\boldsymbol% {\mathrm{{A}}}\boldsymbol{\mathrm{x}}$ .

Graphs

All graphs throughout this paper are assumed to be simple without loss of generality, as collapsing parallel multi-edges does not affect (undirected or directed) graph Laplacians. Moreover, a dynamic update of adding a parallel edge can be simulated by one edge deletion and one edge insertion with combined weight. We denote undirected weighted graphs without an arrow and directed weighted graphs with an arrow, i.e., $G=(V,E,\boldsymbol{\mathrm{w}})$ is an undirected graph with vertices $V$ , edges $E$ , and weights $\boldsymbol{\mathrm{w}}\in\mathbb{R}_{\geq 0}^{E}$ , and $\vec{G}$ is a directed graph. A directed Eulerian graph is a directed graph where weighted in-degree equals weighted out-degree for every vertex. We refer to the vertex set and edge set of a graph $G$ (resp. $\vec{G}$ ) by $V(G)$ and $E(G)$ (resp. $V(\vec{G})$ and $E(\vec{G})$ ). We associate a directed edge $e$ from $u$ to $v$ with the tuple $(u,v)$ , and an undirected edge with $(u,v)$ and $(v,u)$ interchangeably. We define $h(e)=u$ and $t(e)=v$ to be the head and tail of a directed edge $e=(u,v)$ . We let $\textup{rev}(\vec{G})$ denote the directed graph with all edge orientations reversed from $\vec{G}$ , and $\textup{und}(\vec{G})$ denote the undirected graph which removes orientations (both keeping the same weights).

We say $H$ is a subgraph of $G$ if the edges and vertices of $H$ are subsets of the edges and vertices of $G$ (with the same weights), denoting $H=G_{F}$ if $E(H)=F$ , and defining the same notion for directed graphs. For $U\subseteq V$ , we let $G[U]$ denote the induced subgraph of $G$ on $U$ (i.e., keeping all of the edges within $U$ ). When $V$ is a set of vertices, we say $\{V_{i}\}_{i\in[I]}$ is a partition of $V$ if $\bigcup_{i\in[I]}V_{i}=V$ , and all $V_{i}$ are disjoint. We say $\{G_{j}\}_{j\in[J]}$ are a family of edge-disjoint subgraphs of $G=(V,E,\boldsymbol{\mathrm{w}})$ if all $E(G_{j})$ are disjoint, and for all $j\in[J]$ , $V(G_{j})\subseteq V$ , $E(G_{j})\subseteq E$ , and every edge weight in $G_{j}$ is the same as its weight in $G$ .

Graph matrices

For a graph with edges $E$ and vertices $V$ , we let $\boldsymbol{\mathrm{{B}}}\in\{-1,0,1\}^{E\times V}$ be its edge-vertex transfer matrix, so that when $\vec{G}$ is directed and $e=(u,v)$ , $\boldsymbol{\mathrm{{B}}}_{e:}$ is $2$ -sparse with $\boldsymbol{\mathrm{{B}}}_{eu}=1$ , $\boldsymbol{\mathrm{{B}}}_{ev}=-1$ (for undirected graphs, we fix an arbitrary consistent orientation). For $u,v\in V$ , we define $\boldsymbol{\mathrm{b}}_{(u,v)}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}% }\boldsymbol{\mathrm{e}}_{u}-\boldsymbol{\mathrm{e}}_{v}$ . When $\boldsymbol{\mathrm{{B}}}$ is the transfer matrix associated with graph $G=(V,E,\boldsymbol{\mathrm{w}})$ (resp. $\vec{G}$ ), we say $\boldsymbol{\mathrm{x}}$ is a circulation in $G$ (resp. $\vec{G}$ ) if $\boldsymbol{\mathrm{{B}}}^{\top}\boldsymbol{\mathrm{x}}=\boldsymbol{\mathrm{0}% }_{V}$ ; when $G$ (resp. $\vec{G}$ ) is clear we simply say $\boldsymbol{\mathrm{x}}$ is a circulation. We let $\boldsymbol{\mathrm{{H}}},\boldsymbol{\mathrm{{T}}}\in\{0,1\}^{E\times V}$ indicate the heads and tails of each edge, i.e., have one nonzero entry per row indicating the relevant head or tail vertex for each edge, respectively, so that $\boldsymbol{\mathrm{{B}}}=\boldsymbol{\mathrm{{H}}}-\boldsymbol{\mathrm{{T}}}$ . When clear from context that $\boldsymbol{\mathrm{w}}$ are edge weights, we let $\boldsymbol{\mathrm{{W}}}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}% \textbf{{diag}}\left(\boldsymbol{\mathrm{w}}\right)$ . For undirected $G=(V,E,\boldsymbol{\mathrm{w}})$ with transfer matrix $\boldsymbol{\mathrm{{B}}}$ , the Laplacian matrix of $G$ is $\boldsymbol{\mathrm{{L}}}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}% \boldsymbol{\mathrm{{B}}}^{\top}\boldsymbol{\mathrm{{W}}}\boldsymbol{\mathrm{{% B}}}$ . For directed $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ , the directed Laplacian matrix of $\vec{G}$ is $\vec{\boldsymbol{\mathrm{{L}}}}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}% }\boldsymbol{\mathrm{{B}}}^{\top}\boldsymbol{\mathrm{{W}}}\boldsymbol{\mathrm{% {H}}}$ . To disambiguate, we use $\boldsymbol{\mathrm{{L}}}_{G}$ , $\boldsymbol{\mathrm{{H}}}_{G}$ , $\boldsymbol{\mathrm{{T}}}_{G}$ , $\boldsymbol{\mathrm{{B}}}_{G}$ , etc. to denote matrices associated with a graph $G$ when convenient.

Note that $\vec{\boldsymbol{\mathrm{{L}}}}^{\top}\boldsymbol{\mathrm{1}}_{V}=\boldsymbol{% \mathrm{0}}_{V}$ for any directed Laplacian $\vec{\boldsymbol{\mathrm{{L}}}}$ . If $\vec{G}$ is Eulerian, then its directed Laplacian also satisfies $\vec{\boldsymbol{\mathrm{{L}}}}\boldsymbol{\mathrm{1}}_{V}=\boldsymbol{\mathrm% {0}}_{V}$ and $\boldsymbol{\mathrm{w}}$ is a circulation in $\vec{G}$ (i.e., $\boldsymbol{\mathrm{{B}}}^{\top}\boldsymbol{\mathrm{w}}=\boldsymbol{\mathrm{0}% }_{V}$ ). Note that for a directed graph $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ and its corresponding undirected graph $G\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{G})$ , the undirected Laplacian is $\boldsymbol{\mathrm{{L}}}_{G}=\boldsymbol{\mathrm{{B}}}^{\top}\boldsymbol{% \mathrm{{W}}}\boldsymbol{\mathrm{{B}}}$ , and the reversed directed Laplacian is $\vec{\boldsymbol{\mathrm{{L}}}}_{\textup{rev}(\vec{G})}=-\boldsymbol{\mathrm{{% B}}}^{\top}\boldsymbol{\mathrm{{W}}}\boldsymbol{\mathrm{{T}}}$ .

We let $\boldsymbol{\mathrm{\Pi}}_{V}$ denote the Laplacian of the unweighted complete graph on $V$ , i.e., $\boldsymbol{\mathrm{\Pi}}_{V}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}% \mathbf{I}_{V}-\frac{1}{|V|}\boldsymbol{\mathrm{1}}_{V}\boldsymbol{\mathrm{1}}% _{V}^{\top}$ . Note that $\boldsymbol{\mathrm{\Pi}}_{V}$ is the orthogonal projection on the the subspace spanned by the vector that is $1$ in the coordinates of $V$ and $0$ elsewhere.

For a subset of vertices $C\subseteq V$ and $F=V\setminus C$ , the Schur complement of a directed Laplacian $\vec{\boldsymbol{\mathrm{{L}}}}$ onto $C$ is defined by $\operatorname{\mathtt{Sc}}(\vec{\boldsymbol{\mathrm{{L}}}},C)\stackrel{{% \scriptstyle\textup{\tiny def}}}{{=}}\vec{\boldsymbol{\mathrm{{L}}}}_{CC}-\vec% {\boldsymbol{\mathrm{{L}}}}_{CF}\vec{\boldsymbol{\mathrm{{L}}}}_{FF}^{\dagger}% \vec{\boldsymbol{\mathrm{{L}}}}_{FC}$ , which satisfies the block LU factorization

\vec{\boldsymbol{\mathrm{{L}}}}=\begin{pmatrix}\vec{\boldsymbol{\mathrm{{L}}}}% _{FF}&\vec{\boldsymbol{\mathrm{{L}}}}_{FC}\\ \vec{\boldsymbol{\mathrm{{L}}}}_{CF}&\vec{\boldsymbol{\mathrm{{L}}}}_{CC}\end{% pmatrix}=\begin{pmatrix}\boldsymbol{\mathrm{{I}}}_{F}&0\\ \vec{\boldsymbol{\mathrm{{L}}}}_{CF}\vec{\boldsymbol{\mathrm{{L}}}}_{FF}^{% \dagger}&\boldsymbol{\mathrm{{I}}}_{C}\end{pmatrix}\begin{pmatrix}\vec{% \boldsymbol{\mathrm{{L}}}}_{FF}&0\\ 0&\operatorname{\mathtt{Sc}}(\vec{\boldsymbol{\mathrm{{L}}}},C)\end{pmatrix}% \begin{pmatrix}\boldsymbol{\mathrm{{I}}}_{F}&\vec{\boldsymbol{\mathrm{{L}}}}_{% FF}^{\dagger}\vec{\boldsymbol{\mathrm{{L}}}}_{FC}\\ 0&\boldsymbol{\mathrm{{I}}}_{C}\end{pmatrix}.

(2)

A Schur complement of a directed graph Laplacian remains a directed graph Laplacian. We say that a directed graph $\vec{H}$ is the Schur complement of $\vec{G}$ onto a subset $C\subseteq V$ , denoted by $\vec{H}=\operatorname{\mathtt{Sc}}(\vec{G},C)$ , if $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{H}}=\operatorname{\mathtt{Sc}}(\vec{% \boldsymbol{\mathrm{{L}}}},C)$ . The Schur complement of an Eulerian graph is Eulerian.

Cut, Conductance and Expanders

Given a directed graph $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ , for a subset $S\subseteq V$ of vertices, the volume of $S$ is the same as $\textup{vol}_{G}(S)\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\sum_{v\in S% }\sum_{e\in E(G):e\ni v}\boldsymbol{\mathrm{w}}(e)$ the volume of $S$ in the corresponding undirected graph $G=\textup{und}(\vec{G})$ . For another subset $T\subseteq V$ , we let $E(S,T)$ be the set of edges satisfying that for $e\in E(S,T)$ it has $h(e)\in S$ and $t(e)\in T$ and denote by $\boldsymbol{\mathrm{w}}(S,T)\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}% \sum_{e\in E(S,T)}\boldsymbol{\mathrm{w}}(e)$ the total weight of these edges. We say that a subgraph $\vec{C}$ , often referred to as a subset of edges, is a directed cut (di-cut) of $\vec{G}$ if there exists some subset $S\subseteq V$ satisfying $S,V\setminus S\neq\emptyset$ such that $E(\vec{C})=E(S,V\setminus S)$ . The corresponding (undirected) cut $C=\textup{und}(\vec{C})$ of $\vec{C}$ is defined by $E(C)=E_{G}(S,V\setminus S)=E(S,V\setminus S)\cup E(V\setminus S,S)$ the set of cut edges in $G$ .

We say that the undirected conductance of subset $S$ is

\Phi_{G}(S)=\frac{\boldsymbol{\mathrm{w}}_{G}(S,V\setminus S)}{\min\left\{% \textup{Vol}(S),\textup{Vol}(V\setminus S)\right\}},

where we note that $\boldsymbol{\mathrm{w}}_{G}(S,V\setminus S)=\boldsymbol{\mathrm{w}}(S,V% \setminus S)+\boldsymbol{\mathrm{w}}(V\setminus S,S)$ . The conductance of an undirected graph $G$ , denoted by $\phi(G)$ , is the minimum conductance $\phi_{G}(S)$ of any cut $(S,V\setminus S)$ .

Definition 9.

For any $\phi\in(0,1)$ , we say that an undirected graph $G$ is a $\phi$ -expander if $\Phi(G)\geq\phi$ .

3 A Fully Dynamic Directed Spectral Sparsifier

In this section, we give an overview of our main result, Theorem 3 for dynamically maintaining directed spectral sparsifiers under the notion of degree balance preserving directed spectral approximation (Definition 2).

For directed spectral sparsification, a major challenge compared to undirected spectral sparsification is the degree balance preservation requirement. Sampling edges independently, as in undirected spectral sparsification algorithms [46], may create degree imbalances. Recent approaches in the static setting instead use independent sampling of graph structures that inherently preserve degree balances. Chu et al. [16] used short-cycle sampling while Jambulapati et al. [32] employed electrical circulation sampling. These structures are particularly difficult to maintain in a dynamic setting and the recourse could grow quickly over $\Omega(\log n)$ levels of half-sparsifications.

To avoid these issues, we instead adopt the approach of Cohen et al. [20], where the sparsification algorithm performs independent edge sampling on expanders and computes a “patching” graph to fix degree imbalances caused by the sampling. Cohen et al. made the key observation that sampling a directed edge with probability inversely proportional to both the in-degree of its tail and the out-degree of its head in an “expander” (i.e., a directed graph whose corresponding undirected graph is an expander) effectively controls spectral error and degree imbalance. They then showed that a small patching of size $O(n)$ can be computed for such an expander by greedily matching remaining imbalanced degrees.

We show in the full version that a patching similar to the greedy patching of [20] can be implicitly maintained by a tree data structure that allows $\widetilde{O}(1)$ time querying of any edge. We call this an external patching since it introduces directed edges not originally present in the graph. To avoid having extra edges in a sparsifier, we introduce another patching algorithm that slightly adjusts the edge weights of the sampled subgraph using electrical flow. We call this an internal patching algorithm. For our dynamic algorithm, we only update the demand vector associated with the degree imbalance and compute an electric flow when querying the entire graph. We refer readers to the full version for more details.

A significant problem with both patching approaches is that the patching edges cannot be maintained explicitly. For external patching, modifying the degree of a vertex whose interval appears early in the ordering changes almost all edge weights in the patching. It can be worse for internal patching: the entire electrical flow is changed by a single update. To solve this problem, we observe that by adding auxiliary vertices, we can effectively patch degree imbalance using just a single directed star graph with one extra vertex. This approach allows us to maintain the spectral sparsifier explicitly and efficiently, as a single degree change only requires adjusting one edge on the degree imbalance. We remark that there is no tangible drawback for having a few auxiliary vertices in a sparsifier. For Eulerian graphs specifically, sparsifiers constructed this way still serve as effective preconditioners for solving Eulerian systems (see Lemma 13 in Section 3.1). There are also applications of undirected sparsifiers with auxiliary vertices [39, 26].

3.1 Properties of degree balance preserving directed spectral sparsifiers

In this section, we provide some useful properties of our degree balance preserving directed spectral sparsification. Some of these properties are crucial for applying the dynamic sparsification framework of [11]. Proofs of these statements can be found in the full version.

We state first the following equivalent definition of Definition 2 using the degree preserving condition, justifying our naming for Definition 2.

Lemma 10.

$\vec{G}^{\prime}$ is an $\varepsilon$ -degree balance preserving directed spectral approximation of $\vec{G}$ (i.e., satisfying (1)) if and only if $\vec{G}^{\prime}$ is degree balance preserving w.r.t. $\vec{G}$ and

\left\lVert\boldsymbol{\mathrm{{L}}}_{G}^{\frac{\dagger}{2}}\left(\vec{% \boldsymbol{\mathrm{{L}}}}_{\vec{G}}-\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{H}}% \right)\boldsymbol{\mathrm{{L}}}_{G}^{\frac{\dagger}{2}}\right\rVert_{\textup{% op}}\leq\varepsilon.

(3)

Recall the union property of graph sparsification problems. Let $\mathcal{H}(\vec{G},\varepsilon)$ be the set of $\varepsilon$ -approximations of $\vec{G}$ under some definition of approximation for weighted directed (or undirected) graph. Then, we say that $\mathcal{H}$ satisfies union property if for any $G=\bigcup_{i=1}^{k}s_{i}\cdot G_{i}$ with $s_{1},\ldots,s_{k}\in\mathbb{R}_{\geq 0}$ it satisfies that for any $\vec{H}_{i}\in\mathcal{H}(\vec{G}_{i},\varepsilon)$ , we have

\bigcup_{i=1}^{k}s_{i}\cdot\vec{H}_{i}\in\vec{H}(\vec{G},\varepsilon).

Our notion of directed spectral sparsification Definition 2 naturally satisfies the union property.

Lemma 11 (Union property).

Suppose directed graph $\vec{G}=\bigcup_{i=1}^{k}s_{i}\cdot\vec{G}_{i}$ for some $k$ and that $s_{1},\ldots,s_{k}\in\mathbb{R}_{\geq 0}$ . Then, suppose $\vec{G}_{i}^{\prime}$ is an $\varepsilon$ -degree balance preserving directed spectral approximation to $\vec{G}_{i}$ for every $i\in[k]$ , it follows that $\bigcup_{i=1}^{k}s_{i}\vec{G}_{i}^{\prime}$ is an $\varepsilon$ -degree balance preserving directed spectral approximation to $\vec{G}$ .

We state also the contraction property where contraction of vertices does not affect the quality of our degree-balance preserving approximation.

Lemma 12 (Contraction property).

For a directed graph $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ , suppose $\vec{H}$ is an $\varepsilon$ -degree balance preserving directed spectral approximation to $\vec{G}$ . Then, for any subset $W\subseteq V$ , let $\vec{G}^{\prime}$ , $\vec{H}^{\prime}$ be the respective directed graphs resulting from contracting $W$ , then $\vec{H}^{\prime}$ is an $\varepsilon$ -degree balance preserving directed spectral approximation to $\vec{G}^{\prime}$ .

We also demonstrate that having extra vertices in a degree balance preserving sparsifier does not affect most potential applications of it. In particular, Lemma 13 states that as long as the Schur complement of a graph $\vec{H}$ is a good degree balance preserving sparsifier of an Eulerian graph $\vec{G}$ , then $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{H}}^{\dagger}$ serves as a good preconditioner of $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}}$ .

Lemma 13.

Let $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ and $\vec{H}=(V\cup X,E_{\vec{H}},\boldsymbol{\mathrm{w}}_{\vec{H}})$ be directed graphs such that the Schur complement $\operatorname{\mathtt{Sc}}(\vec{H},V)$ is a $\varepsilon$ -degree balance preserving approximation of $\vec{G}$ for $\varepsilon\in(0,\frac{1}{4})$ . If $\vec{G}$ is Eulerian, then

\left\lVert\boldsymbol{\mathrm{{P}}}_{V}-\boldsymbol{\mathrm{{P}}}_{V}\vec{% \boldsymbol{\mathrm{{L}}}}_{\vec{H}}^{\dagger}\vec{\boldsymbol{\mathrm{{L}}}}_% {\vec{G}}\right\rVert_{\boldsymbol{\mathrm{{L}}}_{G}\to\boldsymbol{\mathrm{{L}% }}_{G}}\leq 8\varepsilon.

3.2 Bipartitle lifts

We invoke a helper result which we use to ensure degree preserving properties, a strictly stronger property of degree balance preserving properties, of our algorithms by working with bipartite lifts. This primitive is from Section 9.1 of [32]. Given a directed graph $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ , we let the directed graph $\vec{G}^{\uparrow}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{% blift}(\vec{G})$ be its bipartite lift, which is defined so that $V_{\vec{G}^{\uparrow}}=V\cup\bar{V}$ where $\bar{V}$ is a copy of $V$ , and $E_{\vec{G}^{\uparrow}}=\{f=(u,\bar{v})|(u,v)\in E\}$ with $\boldsymbol{\mathrm{w}}_{(u,\bar{v})}=\boldsymbol{\mathrm{w}}_{(u,v)}$ . Notice that our definition gives a canonical bijection between $E_{\vec{G}^{\uparrow}}$ and $E_{\vec{G}}$ .

Lemma 14.

Let $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ be a directed graph and let its bipartite lift be $\vec{G}^{\uparrow}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}(V\cup V^{% \prime},E^{\uparrow},\boldsymbol{\mathrm{w}})=\textup{blift}(\vec{G})$ , with $G\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{G})$ and $G^{\uparrow}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{% G}^{\uparrow})$ . Suppose that for some $\varepsilon>0$ , $\boldsymbol{\mathrm{w}}^{\prime}\in\mathbb{R}^{E}_{>0}$ satisfies

\boldsymbol{\mathrm{{B}}}_{\vec{G}^{\uparrow}}^{\top}\boldsymbol{\mathrm{w}}^{% \prime}=\boldsymbol{\mathrm{{B}}}_{\vec{G}^{\uparrow}}^{\top}\boldsymbol{% \mathrm{w}},\quad\left\lVert\boldsymbol{\mathrm{{L}}}_{G^{\uparrow}}^{\frac{% \dagger}{2}}\boldsymbol{\mathrm{{B}}}_{\vec{G}^{\uparrow}}^{\top}(\boldsymbol{% \mathrm{{W}}}^{\prime}-\boldsymbol{\mathrm{{W}}})\boldsymbol{\mathrm{{H}}}_{% \vec{G}^{\uparrow}}\boldsymbol{\mathrm{{L}}}_{G^{\uparrow}}^{\frac{\dagger}{2}% }\right\rVert_{\textup{op}}\leq\varepsilon.

Then, letting $|\boldsymbol{\mathrm{{B}}}_{\vec{G}}|$ apply the absolute value entry-wise,

\boldsymbol{\mathrm{{B}}}_{\vec{G}}^{\top}\boldsymbol{\mathrm{w}}^{\prime}=% \boldsymbol{\mathrm{{B}}}_{\vec{G}}^{\top}\boldsymbol{\mathrm{w}},\quad|% \boldsymbol{\mathrm{{B}}}_{\vec{G}}|^{\top}\boldsymbol{\mathrm{w}}^{\prime}=|% \boldsymbol{\mathrm{{B}}}_{\vec{G}}|^{\top}\boldsymbol{\mathrm{w}},\quad\left% \lVert\boldsymbol{\mathrm{{L}}}_{G}^{\frac{\dagger}{2}}\boldsymbol{\mathrm{{B}% }}_{\vec{G}}^{\top}(\boldsymbol{\mathrm{{W}}}^{\prime}-\boldsymbol{\mathrm{{W}% }})\boldsymbol{\mathrm{{H}}}_{\vec{G}}\boldsymbol{\mathrm{{L}}}_{G}^{\frac{% \dagger}{2}}\right\rVert_{\textup{op}}\leq\varepsilon.

For the rest of this section, we almost exclusively considers such directed bipartite graphs.

Lemma 15 states that adding extra vertices and taking the Schur complement onto the original vertices under bipartite lift does not affect approximation guarantees on the unlifted graph.

Lemma 15.

Let $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ be a directed graph and let its bipartite lift be $\vec{G}^{\uparrow}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}(V\cup V^{% \prime},E^{\uparrow},\boldsymbol{\mathrm{w}})=\textup{blift}(\vec{G})$ , with $G\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{G})$ and $G^{\uparrow}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{% G}^{\uparrow})$ . Suppose $\vec{H}=(V\cup V^{\prime}\cup X,E_{\vec{H}},\boldsymbol{\mathrm{w}}_{\vec{H}})$ is a directed graph such that $\operatorname{\mathtt{Sc}}(\vec{H},V\cup V^{\prime})$ is an $\varepsilon$ -degree preserving spectral approximation of $\vec{G}^{\uparrow}$ . Let $\vec{H}^{\downarrow}$ be the resulting directed graph of $\vec{H}$ with each pair of corresponding vertices $\{v,v^{\prime}\}$ contracted. Then, $\operatorname{\mathtt{Sc}}(\vec{H}^{\downarrow},V)$ is an $\varepsilon$ -degree preserving spectral approximation of $\vec{G}$ .

3.3 Reduction to decremental sparsifier on expanders

In this section, we recall a fully dynamic expander decomposition algorithm by [11] using expander pruning from [45].

We first state the definition of expander decompositions. Note that for the purpose of this paper, we assume that the subgraphs in the decomposition contain the entire set of edges.

Definition 16 (Expander decomposition).

We call $(\{G_{i}\}_{i\in[I]})$ a $(\phi,J)$ -expander decomposition if $\{G_{i}\}_{i\in[I]}$ are edge-disjoint subgraphs of $G=(V,E,\boldsymbol{\mathrm{w}})$ satisfying $\bigcup_{i}G_{i}=G$ , and the following hold.

1.

Bounded weight ratio: For all $i\in[I]$ , $\frac{\max_{e\in E(G_{i})}\boldsymbol{\mathrm{w}}_{e}}{\min_{e\in E(G_{i})}% \boldsymbol{\mathrm{w}}_{e}}\leq 2$ .
2.

Conductance: For all $i\in[I]$ , $\Phi(G_{i})\geq\phi$ .
3.

Vertex coverage: There is a $J$ -partition $\bigcup_{j\in[J]}S_{j}=[I]$ such that every vertex $v\in V(G)$ appears at most once in the subgraphs of each $S_{j}$ .

When stating our results, we replace the use of the static expander decomposition algorithm from [45] by the state-of-the-art algorithm in [2].

Lemma 17 (Expander pruning).

Let $G=(V,E,\boldsymbol{\mathrm{w}})$ be a $\phi$ -expander with $\frac{\max_{e\in E}{\boldsymbol{\mathrm{w}}_{e}}}{\min_{e\in E}{\boldsymbol{% \mathrm{w}}_{e}}}\leq 2$ . There is a deterministic algorithm with access to adjacency lists of $G$ such that given an online sequence of $k\leq\frac{\phi m}{10}$ edges deletions in $G$ , can maintain a pruned set $P\subset V$ satisfing the following properties. Let $G_{i},P_{i}$ be the graph and set $P$ after $i$ edge deletions. We have for all $i$

1.

$P_{0}=\emptyset$ , $P_{i}\subseteq P_{i+1}$ ,
2.

$\textup{vol}_{G_{i}}(P_{i})\leq\frac{16i}{\phi}\min_{e\in E}\boldsymbol{% \mathrm{w}}_{e}$ ,
3.

$G_{i}[V\setminus P_{i}]$ is a $\frac{1}{12}\phi$ -expander,
4.

$|E(P_{i},V\setminus P_{i})|\leq 4i$ .

The amortized update time is $O(\phi^{-2}\log m)$ .

Proposition 18 (Dynamic expander decomposition).

Given a weighted undirected dynamic graph $G$ with edge bounded edge weights ratio $\frac{\max_{e\in E}\boldsymbol{\mathrm{w}}_{e}}{\min_{e\in E}\boldsymbol{% \mathrm{w}}_{e}}\leq W$ at all time, there exists a dynamic algorithm against an adaptive adversary that preprocess in $O\left(m\log^{7}n\right)$ time, maintains with high probability a $(C_{\textup{DED}}\log^{-2}(n),(\log(W)+3)(2\log n+3)\log n)$ -expander decomposition over all polynomially bounded number of updates of $G$ with high probability for some constant $C_{\textup{DED}}$ . The algorithm supports both edge deletions and insertions with $O(\log^{2}n)$ amortized recourse and $O(\log^{7}n)$ amortized time.

After each update, the output consists of a list of potential changes to the decomposition: (i) edge deletions to some subgraph in the decomposition, (ii) removing some subgraph from the decomposition, and (iii) new subgraph added to the decomposition.

Crucially, the types of updates in Proposition 18 entails that any expander in the dynamic decomposition only receives decremental update before it becomes obsolete.

We now recall the reduction to decremental algorithm on expanders by [11] using dynamic expander decomposition algorithm from above. The version we present here is an informal statement with a slight generalization: we remove the perturbation requirement and allows for directed graphs. See full version for more details.

Lemma 19 (Informal blackbox reduction with dynamic expander decomposition).

Assume $\mathcal{H}$ is a graph sparsification problem that satisfies the union property, and there is a decremental algorithm $\mathcal{A}$ for $\mathcal{H}$ on (directed) graphs with edge weights ratio at most $2$ and satisfying that their corresponding undirected graph is an expander.

Then, there exists a fully dynamic algorithm $\mathcal{B}$ for $\mathcal{H}$ on weighted (directed) graphs such that given a dynamic weighted simple directed graph $\vec{G}$ maintains an $\varepsilon$ -approximate sparsifier of essentially the same size with essentially the same amortized update time as $\mathcal{A}$ .

3.4 Patching by directed star graphs

To fix the degree imbalance, we consider patching using directed star graphs. The static algorithm PatchingStar (Algorithm 1) can be trivially made dynamic with deterministic updates in $O(1)$ worst-case update time and recourse. This dynamic algorithm can also maintain the guarantees in Lemma 20.

Lemma 20 (Star patching).

Given $\vec{G}$ , $\boldsymbol{\mathrm{w}}^{\prime}$ as in the input conditions and $\xi$ satisfying that $\xi[\boldsymbol{\mathrm{d}}^{\prime}]^{(\textup{o})}\leq\boldsymbol{\mathrm{d}% }^{(\textup{o})}$ and $\xi[\boldsymbol{\mathrm{d}}^{\prime}]^{(\textup{i})}\leq\boldsymbol{\mathrm{d}% }^{(\textup{i})}$ for $[\boldsymbol{\mathrm{d}}^{\prime}]^{(\textup{i})},[\boldsymbol{\mathrm{d}}^{% \prime}]^{(\textup{o})}$ the in and out degrees of $\vec{G}^{\prime}=(V,E,\boldsymbol{\mathrm{w}}^{\prime})$ , PatchingStar (Algorithm 1) returns in time $O(m)$ a simple weighted directed graph $\vec{H}$ such that

1.

$\boldsymbol{\mathrm{d}}^{(\textup{o})}=[\boldsymbol{\mathrm{d}}^{(\textup{o})}% _{\vec{H}}]_{V}$ , $\boldsymbol{\mathrm{d}}^{(\textup{i})}=[\boldsymbol{\mathrm{d}}^{(\textup{i})}% _{\vec{H}}]_{V}$ , and for the Schur complement $\vec{S}=\operatorname{\mathtt{Sc}}(\vec{H},V)$ , $\boldsymbol{\mathrm{d}}^{(\textup{o})}_{\vec{S}}=\boldsymbol{\mathrm{d}}^{(% \textup{o})}_{\vec{H}}$ , $\boldsymbol{\mathrm{d}}^{(\textup{i})}_{\vec{S}}=\boldsymbol{\mathrm{d}}^{(% \textup{i})}_{\vec{H}}$ ,

2.

		$\displaystyle\left\lVert[\boldsymbol{\mathrm{{D}}}^{(\textup{i})}]^{\frac{{% \dagger}}{2}}\left(\operatorname{\mathtt{Sc}}(\vec{\boldsymbol{\mathrm{{L}}}}_% {\vec{H}},V)-\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}^{\prime}}\right)[% \boldsymbol{\mathrm{{D}}}^{(\textup{o})}]^{\frac{{\dagger}}{2}}\right\rVert_{% \textup{op}}$
	$\displaystyle\leq$	$\displaystyle(1-\xi)+\max\left\{\left\lVert\boldsymbol{\mathrm{1}}_{R}-[% \boldsymbol{\mathrm{{D}}}^{(\textup{i})}]^{\dagger}[\boldsymbol{\mathrm{d}}^{% \prime}]^{(\textup{i})}\right\rVert_{\infty},\left\lVert\boldsymbol{\mathrm{1}% }_{C}-[\boldsymbol{\mathrm{{D}}}^{(\textup{o})}]^{\dagger}[\boldsymbol{\mathrm% {d}}^{\prime}]^{(\textup{o})}\right\rVert_{\infty}\right\},$

3.

$m_{\vec{H}}\leq\textup{nnz}(\boldsymbol{\mathrm{w}}^{\prime})+n$ and $|V_{\vec{H}}|=n+1$ .

Algorithm 1

\textsc{PatchingStar}(\vec{G}=(V,E,\boldsymbol{\mathrm{w}}),\boldsymbol{% \mathrm{w}}^{\prime},\xi)

.

3.5 A simple decremental algorithm on expanders

Finally, we present our main ingredient for a fully dynamic spectral sparsifier: a decremental algorithm for maintaining a degree preserving directed spectral sparsifier for an expander.

Lemma 21.

Suppose $\vec{G}=(C\cup R,E,\boldsymbol{\mathrm{w}})$ is a weighted directed bipartite graph with edges $E\subseteq C\times R$ and weight ratio $\frac{\max_{e\in E}\boldsymbol{\mathrm{w}}_{e}}{\min_{e\in E}\boldsymbol{% \mathrm{w}}_{e}}\leq 2$ undergoing edge deletions only. There is a dynamic algorithm that preprocesses in time $O(m)$ , maintains explicitly a directed graph $\vec{H}$ on vertices $C\cup R\cup\{x\}$ and $m_{\vec{H}}=O(\varepsilon^{-2}\phi^{-4}N\log n)$ , where $N$ is the number of non-trivial vertices currently. The algorithm has worst-case recourse and update time $O(\varepsilon^{-2}\phi^{-8}\log^{2}n)$ . Furthermore, with high probability whenever $G=\textup{und}(\vec{G})$ becomes a $\phi$ -expander, $\operatorname{\mathtt{Sc}}(\vec{H},C\cup R)$ is an $\varepsilon$ -degree preserving directed spectral sparsifier of $\vec{G}$ .

The following Lemma 22 is the key lemma from [20] that enables our results. In light of our static algorithm, our dynamic algorithm maintains a reweighted subgraph $\vec{G}^{\prime}$ satisfying the approximation guarantees in (4) for its weighted adjacency matrix $\boldsymbol{\mathrm{{A}}}^{\prime}=\boldsymbol{\mathrm{{T}}}^{\top}\boldsymbol% {\mathrm{{W}}}^{\prime}\boldsymbol{\mathrm{{H}}}$ with $\boldsymbol{\mathrm{{R}}}=\boldsymbol{\mathrm{{D}}}^{(\textup{i})}$ and $\boldsymbol{\mathrm{{C}}}=\boldsymbol{\mathrm{{D}}}^{(\textup{o})}$ . For brevity we say that $\vec{G}^{\prime}$ is an $\varepsilon$ -degree approximation of $\vec{G}$ .

Lemma 22.

Let $\boldsymbol{\mathrm{{A}}}\in\mathbb{R}_{\geq 0}^{n_{1}\times n_{2}}$ be a matrix with $m\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{nnz}(\boldsymbol{% \mathrm{{A}}}),n\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}(n_{1}+n_{2})$ and parameters $\varepsilon,\delta\in(0,1)$ . Let the row and column sums be $\boldsymbol{\mathrm{r}}=\boldsymbol{\mathrm{{A}}}\boldsymbol{\mathrm{1}}_{d_{2}}$ and $\boldsymbol{\mathrm{c}}=\boldsymbol{\mathrm{{A}}}^{\top}\boldsymbol{\mathrm{1}% }_{d_{1}}$ with $\boldsymbol{\mathrm{{R}}}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}% \textbf{{diag}}\left(\boldsymbol{\mathrm{r}}\right)$ and $\boldsymbol{\mathrm{{C}}}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}% \textbf{{diag}}\left(\boldsymbol{\mathrm{c}}\right)$ . Consider a random matrix $\widetilde{\boldsymbol{\mathrm{{A}}}}\in\mathbb{R}_{\geq 0}^{n_{1}\times n_{2}}$ that independently for each nonzero $\boldsymbol{\mathrm{{A}}}_{ij}$

\widetilde{\boldsymbol{\mathrm{{A}}}}_{ij}=\begin{cases}\frac{1}{p_{ij}}% \boldsymbol{\mathrm{{A}}}_{ij}&\mbox{with probability\nobreak\ }p_{ij}\geq\min% \left\{1,\rho\boldsymbol{\mathrm{{A}}}_{ij}\left(\frac{1}{\sqrt{\boldsymbol{% \mathrm{r}}_{i}\boldsymbol{\mathrm{c}}_{j}}}\right)\right\}\\ 0&\mbox{otherwise,}\end{cases}

where $\rho=C_{\textup{SS}}\cdot\varepsilon^{-2}\log\frac{3n}{\delta}$ . Then, it satisfies that with probability $\geq 1-\delta$ , the following holds

\left\lVert\boldsymbol{\mathrm{{R}}}^{\frac{{\dagger}}{2}}(\widetilde{% \boldsymbol{\mathrm{{A}}}}-\boldsymbol{\mathrm{{A}}})\boldsymbol{\mathrm{{C}}}% ^{\frac{{\dagger}}{2}}\right\rVert_{\textup{op}}\leq\varepsilon,\quad\left% \lVert\boldsymbol{\mathrm{{R}}}^{{\dagger}}(\widetilde{\boldsymbol{\mathrm{{A}% }}}-\boldsymbol{\mathrm{{A}}})\boldsymbol{\mathrm{1}}_{n_{2}}\right\rVert_{% \infty}\leq\varepsilon,\quad\left\lVert\boldsymbol{\mathrm{{C}}}^{{\dagger}}(% \widetilde{\boldsymbol{\mathrm{{A}}}}-\boldsymbol{\mathrm{{A}}})^{\top}% \boldsymbol{\mathrm{1}}_{n_{1}}\right\rVert_{\infty}\leq\varepsilon.

(4)

Algorithm 2

\textsc{DegreeSparsifyPreprocess}(\vec{G}=(V,E,\boldsymbol{\mathrm{w}}),% \varepsilon,\delta)

.

Algorithm 3

\textsc{DegreeSparsifyDelete}(e)

.

Similar to the algorithm in [11], Algorithms 2, 3 sample for each vertex a subset of its incident edges using a fast uniform subset sampling algorithm [35, 22, 12]. An edge $e=(u,v)$ is present in the sparsifier as long as one of $u, v$ has it sampled.

Lemma 23.

Under the same assumptions on $\vec{G},\varepsilon,\phi$ as in Lemma 21, there is an algorithm that given an oblivious online sequence of edge deletions, preprocesses in time $O(m)$ , maintains explicitly a reweighted directed subgraph $\vec{G}^{\prime}$ that is an $\varepsilon$ -degree approximation of $\vec{G}$ with $\textup{nnz}(\boldsymbol{\mathrm{w}}^{\prime})=O(\varepsilon^{2}N\log n)$ where $N$ is the number of non-trivial vertices currently. The algorithm has worst-case recourse $O(\varepsilon^{-2}\log n)$ and worst-case update time $O(\varepsilon^{-2}\log^{2}n)$ .

Our main theorem of this section, Theorem 3, follows by combining our decremental sparsifier on expander in Lemma 21 and the dynamic expander decomposition framework in Lemma 19.

3.6 Degree preserving directed spectral sparsification

In this section, we show to extend the degree-balance preserving guarantee from the algorithms above to exact degree preserving, i.e., the algorithm maintains a sparsifier with exact same weighted in and out degrees as the input directed graph. Even though our algorithms are degree preserving on bipartite lifted graphs, the patching schemes, except internal patching, may introduce self-loops when “unlifting” the sparsifier back to the original set of vertices. Eliminating the center of a star creates a biclique on all of its adjacent vertices. If there was an edge $(v,x)$ and $(x,v^{\prime})$ for center $x$ , then the biclique contains the degenerative edge of $(v,v^{\prime})$ , making it not degree preserving.

To avoid self-loops, we instead consider using multiple stars. We ensure for each star that the incident edges of the center do not contain any pair of edges of the form $(v,x)$ , $(x,v^{\prime})$ . For vertex sets $V,V^{\prime}$ , and the complete set of bipartite edges $E=V\times V^{\prime}$ , we devise a decomposition. Firstly, we label the vertices of $V$ by $[n]$ where $n=|V|$ and denote by $l$ its labeling. For each $v^{\prime}$ that corresponds to $v$ , we assign it the same label. Then, we defined for each integer $i\in[1,\left\lceil\log_{2}(n)\right\rceil]$ the edge set $E_{i}$ by

(u,v^{\prime})\in E_{i}\quad\text{if }\left\lfloor\frac{l(u)}{2^{i-1}}\right% \rfloor\neq\left\lfloor\frac{l(v^{\prime})}{2^{i-1}}\right\rfloor\text{ and }% \left\lfloor\frac{l(u)}{2^{i}}\right\rfloor=\left\lfloor\frac{l(v^{\prime})}{2% ^{i}}\right\rfloor.

We then get the following disjoint decomposition of $E$ ,

E=\{(v,v^{\prime})|v\in V\}\cup\left(\bigcup_{i=1}^{\left\lceil\log_{2}(n)% \right\rceil}E_{i}\right).

To produce a degree preserving directed spectral sparsifier, we first decompose the bipartite lift $\vec{G}^{\uparrow}=(V\cup V^{\prime},F,\boldsymbol{\mathrm{w}})$ into $\left\lceil\log_{2}(n)\right\rceil$ edges disjoint subgraphs where each $\vec{G}_{i}$ only contains the edges $F\cap E_{i}$ . Our dynamic algorithm then proceeds the same as before, with one copy of the algorithm on each $\vec{G}_{i}$ . Now, suppose the algorithm receives an update (insertion or deletion) with edge $e=(u,v^{\prime})$ , we first check for which $E_{i}$ the edge $e$ belongs to. The update is then propagated to the copy on $\vec{G}_{i}^{\uparrow}$ and processed. Our final sparsifier $\vec{H}$ is a union of our degree preserving sparsifiers $\vec{H}_{i}^{\uparrow}$ of each $\vec{G}_{i}^{\uparrow}$ unlifted back to the original set of vertices. The correctness of these operations are guaranteed by Lemmas 11 and 15. We summarize our conclusion above into the following informal statement.

Theorem 24 (Theorem 3, degree preserving).

Given a directed graph $\vec{G}$ on vertices $V$ and with polynomially bounded edge weights, we can maintain explicitly a graph $\vec{H}$ on vertices $V\cup X$ such that the Schur complement $\operatorname{\mathtt{Sc}}(\vec{H},V)$ onto the original vertices is a $\varepsilon$ -degree preserving directed spectral sparsifier of $\vec{G}$ . $\vec{H}$ has size $\widetilde{O}(\varepsilon^{-2}n)$ and satisfies $|X|=\widetilde{O}(n)$ . The algorithm has amortized recourse and update time $\widetilde{O}(\varepsilon^{-2})$ per edge insertion or deletion and works against an oblivious adversary.

4 A Fully Dynamic Balanced Directed Cut Sparsifier

In this section we give an overview of our fully dynamic algorithms for maintaining a $\beta$ -balanced directed cut sparsifier under edges updates.

In the static setting, Cen, Cheng, Panigrahi, and Sun [13] initiated the study of $\beta$ -balanced directed cut sparsification. Cen et al. [13] achieved $O(\varepsilon^{-2}\beta n\log n)$ sparsity by independent edge sampling with probability proportional to inverses of undirected edge strength defined originally by Benczúr and Karger [9] for undirected cut sparsification. As it stands, there is currently no known algorithm for fast maintenance of edge strength or fast certification of large edge strength under edge updates. We instead turn our attention to undirected edge connectivity that is proven to be useful for undirected cut sparsification in the work of [27]. We show statically that a $\beta$ -balanced dicut sparsifier can also be obtained by sampling using undirected edge connectivity in Theorem 6.

Definition 25 (Edge connectivity).

For any pair of vertices $u,v\in V$ in a weighted undirected graph $G=(V,E,\boldsymbol{\mathrm{w}})$ , the edge connectivity $\boldsymbol{\mathrm{k}}_{uv}$ between $u, v$ is defined as the minimum value of a cut that separates them. The connectivity of an edge $e=(u,v)$ is defined by $\boldsymbol{\mathrm{k}}_{e}=\boldsymbol{\mathrm{k}}_{uv}$ .

If an undirected graph is an expander, its edge connectivities can be certified by the degrees.

Lemma 26.

For $\phi$ -expander $G=(V,E,\boldsymbol{\mathrm{w}})$ it satisfies that for ever edge $e\in E$ , the edge connectivity $\boldsymbol{\mathrm{k}}_{e}\geq\phi\cdot\min_{v\ni e}\boldsymbol{\mathrm{d}}_{v}$ .

One can then leverage expander decompositions to devise a fast algorithm for directed cut sparsifications. Such an algorithm lends itself nicely to the dynamic setting by utilizing the dynamic expander decomposition framework presented in Section 3.3.

Theorem 27.

Given a directed graph with polynomially bounded edge weights, we can maintain explicitly a $(\beta,\varepsilon)$ -balanced directed cut sparsifier of size $\widetilde{O}(\varepsilon^{-2}\beta n)$ with amortized update time $\widetilde{O}(\varepsilon^{-2}\beta)$ per edge insertion or deletion against an oblivious adversary.

Our de-amortized result in Theorem 5 uses instead the dynamic framework developed by [1]. While it is possible to directly apply the black-box reduction developed in [11] for this task, their framework introduces significant runtime overhead since it is geared towards reduction of dynamic algorithms for adaptive adversary. The algorithm by [1] dynamically maintains bundles of approximate maximum spanning forests (called $\alpha$ -MSFs), that can certify edges with small undirected edge connectivities. We refer readers to the full version for more details on this approach.

Before we present our sparsification algorithms, we state a useful property of $\beta$ -balanced dicut approximations. In the full version, we give these properties for a more general notion of cut approximation on digraphs.

Lemma 28 (Union property).

Suppose directed graph $\vec{G}=\bigcup_{i=1}^{k}s_{i}\cdot\vec{G}_{i}$ for some $k$ and that $s_{1},\ldots,s_{k}\in\mathbb{R}_{\geq 0}$ . Then, suppose $\vec{H}_{i}$ is a $(\beta,\varepsilon)$ -balanced dicut approximation to $\vec{G}_{i}$ for every $i\in[k]$ , it follows that $\bigcup_{i=1}^{k}s_{i}\vec{H}_{i}$ is a $(\beta,\varepsilon)$ -balanced dicut approximation to $\vec{G}$ .

4.1 Balanced directed cut sparsifiers via edge connectivity

Our static algorithm samples directed edges based on the reciprocals of their undirected edge connectivity measures. Proposition 29 quantifies the number of edges in a sparsifier.

Proposition 29.

For a connected undirected graph $G=(V,E,\boldsymbol{\mathrm{w}})$ with edge connectivity $\boldsymbol{\mathrm{k}}$ ,

\sum_{e\in E}\frac{\boldsymbol{\mathrm{w}}_{e}}{\boldsymbol{\mathrm{k}}_{e}}=n% -1.

(5)

We say that $\tilde{\boldsymbol{\mathrm{k}}}$ is a $\ell$ -stretch edge connectivity estimation of $G$ if $\tilde{\boldsymbol{\mathrm{k}}}_{e}\leq\boldsymbol{\mathrm{k}}_{e}$ for all $e$ and

\sum_{e\in E}\frac{\boldsymbol{\mathrm{w}}_{e}}{\tilde{\boldsymbol{\mathrm{k}}% }_{e}}\leq\ell\cdot\sum_{e\in E}\frac{\boldsymbol{\mathrm{w}}_{e}}{\boldsymbol% {\mathrm{k}}_{e}}.

Definition 30.

An edge is $k$ -heavy if its connectivity is at least $k$ ; otherwise, it is said to be $k$ -light. The $k$ -projection of a cut is the set of $k$ -heavy edges in it.

The key to our analysis is the following cut counting statement in Theorem 31 that is a generalization of Theorem 2.3 of [27] to weighted graphs. Crucially, Theorem 31 allows us to bound the number of distinct $k$ -projections polynomially, allowing us to obtain high probability concentration.

Theorem 31 (Generalized cut projection counts, [27]).

For a weighted undirected graph $G$ , any $k\geq\lambda$ and any $\alpha\geq 1$ , the number of distinct $k$ -projections in cuts of value at most $\alpha k$ in $G$ is at most $n^{C_{\textup{cpc}}\alpha}$ , where $\lambda$ is the minimum value of a cut in $G$ and $C_{\textup{cpc}}\geq 2$ is a constant.

Similar to [27], we partition the edges in $\vec{G}$ according to their edge connectivities in $G$ into sets $F_{0},F_{1},\ldots,F_{K}$ , where $K=\left\lceil\log\frac{\max_{e\in E}\boldsymbol{\mathrm{k}}_{e}}{\lambda}\right\rceil$ where $\lambda=\min_{e\in E(G)}\boldsymbol{\mathrm{k}}_{e}$ is the min-cut value of $G$ and

F_{i}=\{e\in E:2^{i}\lambda\leq\boldsymbol{\mathrm{k}}_{e}\leq(2^{i+1}-1)% \lambda\}.

(6)

For a dicut $\vec{C}$ in $\vec{G}$ induced by a partition of the vertices $(S,V\setminus S)$ , we let $C$ be the cut induced by $(S,V\setminus S)$ on $G$ . Let $F_{i}^{(\vec{C})}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}F_{i}\cup\vec% {C}$ and let $f_{i}^{(\vec{C})}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\boldsymbol{% \mathrm{w}}(F_{i}^{(\vec{C})})$ . We also let $F_{i}^{(C)}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}F_{i}\cup C$ and let $f_{i}^{(C)}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\boldsymbol{\mathrm% {w}}(F_{i}^{(C)})$ . Lemma 32 shows that for each $i$ , Algorithm 4 achieves $\beta$ -balanced dicut approximation on subset $F_{i}$ .

Lemma 32.

For any fixed $i$ , with probability at least $1-\frac{\delta}{2n^{2}}$ , every cut $\vec{C}$ in $\vec{G}$ satisfies

\left|f_{i}^{(\vec{C})}-\tilde{f}_{i}^{(\vec{C})}\right|\leq\varepsilon\cdot% \sqrt{\frac{f_{i}^{(\vec{C})}f_{i}^{(C)}}{\beta+1}}

(7)

where $\tilde{f}_{i}^{(\vec{C})}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}% \boldsymbol{\mathrm{w}}_{\vec{H}}(F_{i}^{(\vec{C})})$ .

Algorithm 4

\textsc{SparsifyDiCut}(\vec{G}=(V,E,\boldsymbol{\mathrm{w}}),\beta,\varepsilon% ,\delta,\tilde{\boldsymbol{\mathrm{k}}})

.

Our proof of Lemma 32 follows by showing using concentration bounds that for each $i$ , the probability of (7) fails is at most $\delta\cdot n^{-\Omega(2^{j+2})}$ . Combining this observation with Theorem 31 allows us to obtain the desired probability via a union bound. Then, Theorem 6 follows by applying Cauchy-Schwarz with Lemma 32. See full version for more details.

4.2 Dynamic directed cut sparsification

Since $\beta$ -balanced dicut approximation satisfies union property (Lemma 28), the reductions presented in Section 3.3 can, again, be applied for dynamic balanced dicut sparsification. This allows us to focus on deriving a decremental algorithm on expanders for this task. Specifically, we observe that Algorithms 2, 3 for dynamically maintaining $\varepsilon$ -degree approximations applies here as well.

Lemma 33.

Suppose $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ is a weighted directed graph with weight ratio $\frac{\max_{e\in E}\boldsymbol{\mathrm{w}}_{e}}{\min_{e\in E}\boldsymbol{% \mathrm{w}}_{e}}\leq 2$ undergoing edge deletions only. There is an algorithm that given $\varepsilon,\phi\in(0,1)$ , $\beta\geq 1$ and an oblivious online sequence of edge deletions, preprocesses in time $O(m)$ , maintains explicitly a reweighted directed subgraph $\vec{G}^{\prime}$ of $\vec{G}$ with $\textup{nnz}(\boldsymbol{\mathrm{w}}^{\prime})=O(\varepsilon^{2}\beta\phi^{-1}% N\log n)$ where $N$ is the number of non-trivial vertices currently. The algorithm has worst-case recourse $O(\varepsilon^{-2}\phi^{-1}\beta\log n)$ and worst-case update time $O(\varepsilon^{-2}\phi^{-1}\beta\log^{2}n)$ . Furthermore, with high probability, whenever $G=\textup{und}(\vec{G})$ becomes a $\phi$ -expander, $\vec{H}$ is a $(\beta,\varepsilon)$ -dicut sparsifier of $\vec{G}$ .

Theorem 27 follows by applying the dynamic expander decomposition framework in Lemma 19.

5 Directed Spectral Sparsification Against an Adaptive Adversary via Partial Symmetrization

In this section, we consider the problem of fully dynamic degree balance preserving directed spectral sparsification against an adaptive adversary. This is a particularly difficult question, as the state-of-the-art adaptive undirect spectral sparsifier requires $O(\log n)$ multiplicative approximation [11], while any current notions of directed spectral sparsification do not permit approximation factor $\varepsilon>1$ . As was observed by Kyng, Meierhans, and Probst Gutenberg [37], a weaker notion of approximation, i.e., approximate pseudoinverse (Definition 7), suffices for solving directed Eulerian Laplacian systems.

The key observation in [37] is that a $\beta$ -partial symmetrization $\vec{G}^{(\beta)}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\beta\cdot G% \cup\vec{G}$ of a Eulerian directed graph $\vec{G}$ is a good approximate pseudoinverse of $\vec{G}$ .

Definition 34 (Generalized partial symmetrization, [37]).

For a directed graph $\vec{G}$ with $G\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{G})$ and $\beta\geq 0$ , we let $\vec{G}^{(\beta)}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\beta\cdot G% \cup\vec{G}$ be the $\beta$ -partial symmetrization of $\vec{G}$ .

We remark that $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}^{(\beta)}}=\beta\boldsymbol{\mathrm{{% L}}}_{G}+\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}}$ and $\boldsymbol{\mathrm{{L}}}_{G^{(\beta)}}=(2\beta+1)\boldsymbol{\mathrm{{L}}}_{G}$ where $G^{(\beta)}=\textup{und}(\vec{G}^{(\beta)})$ . Subsequently, one can sparsify the directed portion of $\vec{G}^{(\beta)}$ much more aggressively under the notion of degree balance preserving spectral approximation, since

\left\lVert\boldsymbol{\mathrm{{L}}}_{G^{(\beta)}}^{\frac{{\dagger}}{2}}(\vec{% \boldsymbol{\mathrm{{L}}}}_{\vec{G}}-\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{H}}% )\boldsymbol{\mathrm{{L}}}_{G^{(\beta)}}^{\frac{{\dagger}}{2}}\right\rVert_{% \textup{op}}=\frac{1}{2\beta+1}\left\lVert\boldsymbol{\mathrm{{L}}}_{G}^{\frac% {{\dagger}}{2}}(\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}}-\vec{\boldsymbol{% \mathrm{{L}}}}_{\vec{H}})\boldsymbol{\mathrm{{L}}}_{G}^{\frac{{\dagger}}{2}}% \right\rVert_{\textup{op}}.

Moreover, the graph $\beta G\cup\vec{H}$ is also a good approximate pseudoinverse of $\vec{G}^{(\beta)}$ . One can further reduce the size of the graph by performing an undirected spectral sparsification of the undirected portion $\beta G$ . These layers of sparsification allows them to build sparse preconditioner chain which can be used in solving directed Eulerian Laplacian systems by applying an iterative solver, such as Preconditioned Richardson (see Lemma 35). We refer readers to [37] and [20] for further expositions of this idea.

Lemma 35 (Preconditioned Iterations, Lemma 4.4 in [20]).

If $\boldsymbol{\mathrm{{Z}}}$ is a $\lambda$ -approximate pseudoinverse of $\boldsymbol{\mathrm{{M}}}$ with respect to $\boldsymbol{\mathrm{{U}}}$ for $\lambda\in(0,1)$ , $\boldsymbol{\mathrm{b}}\perp\ker(\boldsymbol{\mathrm{{M}}}^{\top})$ and $N\geq 0$ , then $\boldsymbol{\mathrm{x}}_{N}=\textsc{PreconRichardson}(\boldsymbol{\mathrm{{M}}% },\boldsymbol{\mathrm{{Z}}},\boldsymbol{\mathrm{b}},N)$ computes $\boldsymbol{\mathrm{x}}_{N}=\boldsymbol{\mathrm{{Z}}}_{N}\boldsymbol{\mathrm{b}}$ for some matrix $\boldsymbol{\mathrm{{Z}}}_{N}$ only depending on $\boldsymbol{\mathrm{{Z}}},\boldsymbol{\mathrm{{M}}},$ and $N$ , such that $\boldsymbol{\mathrm{{Z}}}_{N}$ is a $\lambda^{N}$ -approximate pseudoinverse of $\boldsymbol{\mathrm{{M}}}$ with respect to $\boldsymbol{\mathrm{{U}}}$ .

Following [37], we consider for $\vec{G}_{0}=\vec{G}$ , three graphs $\vec{G}_{1},\vec{G}_{2},\vec{G}_{3}$ , such that each $\vec{G}_{i+1}$ spectrally approximates $\vec{G}_{i}$ . Specifically,

1.

$\vec{G}_{1}=\vec{G}_{0}^{(\beta)}$ is the $\beta$ -partial symmetrization of $\vec{G}_{0}$ ,
2.

$\vec{G}_{2}=\beta\cdot G\cup\vec{H}_{2}$ is a sparsification of the directed portion $\vec{G}$ of $\vec{G}_{1}$ ,
3.

$\vec{G}_{3}=\beta\cdot H_{3}\cup\vec{H}_{2}$ , the final sparsifier, further sparsifies the undirected portion of $\beta\cdot G$ of $\vec{G}_{2}$ .

We now recall the definition of a sparsification quadruple.

Definition 36 (Sparsification quadruple, [37]).

We call strongly connected Eulerian graphs $\vec{G}_{0},\vec{G}_{1},\vec{G}_{2},\vec{G}_{3}$ a $(\gamma,\beta,\alpha)$ -quadruple if

1.

$\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{i}}^{\dagger}$ is a $1-\frac{1}{\gamma}$ -approximate pseudoinverse of $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{i-1}}$ with respect to $\boldsymbol{\mathrm{{L}}}_{G_{i}}$ for $i=1,2,3$ ,
2.

$\frac{1}{\gamma}\boldsymbol{\mathrm{{L}}}_{G_{i-1}}\preccurlyeq\boldsymbol{% \mathrm{{L}}}_{G_{i}}\preccurlyeq\gamma\boldsymbol{\mathrm{{L}}}_{G_{i-1}}$ for $i=1,2,3$ ,
3.

$\boldsymbol{\mathrm{d}}^{(\textup{i})}_{\vec{G}_{0}}=\boldsymbol{\mathrm{d}}^{% (\textup{o})}_{\vec{G}_{0}}=(1+\beta)\boldsymbol{\mathrm{d}}^{(\textup{i})}_{% \vec{G}_{i}}=(1+\beta)\boldsymbol{\mathrm{d}}^{(\textup{o})}_{\vec{G}_{i}}$ for $i=1,2$ , and $\boldsymbol{\mathrm{d}}^{(\textup{i})}_{\vec{G}_{0}}=(1+\frac{\beta}{\alpha})% \boldsymbol{\mathrm{d}}^{(\textup{i})}_{\vec{G}_{3}}=(1+\frac{\beta}{\alpha})% \boldsymbol{\mathrm{d}}^{(\textup{o})}_{\vec{G}_{3}}$ ,
4.

$\vec{G}_{3}$ is nearly-linear in $n$ and $m(\vec{G}_{i})=O(m)$ for $i=1,2$ .

Our adaptive degree (balance) preserving directed spectral sparsification algorithm maintains explicitly a sparsification quadruple. Similar to Theorem 3, our sparsifiers in Theorem 8 contain a few extra vertices and the approximation guarantees are given for the Schur complements with those vertices removed. Having such extra vertices does not affect preconditioning, as we observed in Lemma 13. When the input graph $\vec{G}$ becomes Eulerian, for a constant approximate pseudoinverse of $\vec{G}_{3}$ , we can solve the system of linear equation using at most $\textup{polylog}(n,\varepsilon^{-1})$ applications of the pseudoinverse and each matrix $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{i}}$ for $i=1,2,3$ using Lemma 35.

5.1 Sparsification quadruples

In this section, we consider the approximation factors between each $\vec{G}_{i}$ and $\vec{G}_{i+1}$ under the notion of approximate pseudoinverse.

Lemma 37 (Lemma 4.6, [37]).

For Eulerian $\vec{G}_{1}=\vec{G}_{0}^{(\beta)}$ , the matrix $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{1}}^{\dagger}$ is an $(1-\frac{1}{1+2\beta})$ -approximate pseudoinverse of $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{0}}$ with respect to $\boldsymbol{\mathrm{{L}}}_{G_{1}}$ for $G_{1}\stackrel{{\scriptstyle\textup{\tiny def}}}{{=}}\textup{und}(\vec{G}_{1})$ .

Lemma 38 states that if $\vec{G}_{2}$ is a good degree balance preserving spectral approximate to $\vec{G}_{1}$ , then it is also a good approximate pseudoinverse.

Lemma 38.

For $\beta>0$ , $\varepsilon\in(0,1)$ and Eulerian $\vec{G}$ , if $\vec{G}_{2}$ is a $\varepsilon$ -degree balance preserving directed spectral approximation of $\vec{G}_{1}$ and is Eulerian, then $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{2}}^{\dagger}$ is a $\frac{\varepsilon\cdot(2\beta+1)}{\beta}$ -approximate pseudoinverse of $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{1}}$ with respect to $\boldsymbol{\mathrm{{L}}}_{\vec{G}_{2}}$ and $(1-\frac{1}{2\beta+1})\cdot\boldsymbol{\mathrm{{L}}}_{G_{1}}\preccurlyeq% \boldsymbol{\mathrm{{L}}}_{G_{2}}\preccurlyeq(1+2\varepsilon)\cdot\boldsymbol{% \mathrm{{L}}}_{G_{1}}$ .

Similarly, Lemma 40 states that using a good multiplicative undirected spectral approximation to $G$ , one can generate $\vec{G}_{3}$ that is also a good approximate pseudoinverse of $\vec{G}_{2}$ . Here, we recall the definition of multiplicative undirected spectral approximation.

Definition 39 (Undirected spectral approximation, multiplicative).

$H=(V,E_{H},\boldsymbol{\mathrm{w}}_{H})$ is a $\gamma$ -spectral approximation of $G=(V,E,\boldsymbol{\mathrm{w}})$ if it satisfies for some scaler $\eta$ that

\boldsymbol{\mathrm{{L}}}_{G}\preccurlyeq\eta\boldsymbol{\mathrm{{L}}}_{H}% \preccurlyeq\gamma\cdot\boldsymbol{\mathrm{{L}}}_{G}.

Lemma 40.

For $\lambda>1$ and Eulerian $\vec{G}$ , if the graph $H$ satisfies $\boldsymbol{\mathrm{{L}}}_{G}\preccurlyeq\boldsymbol{\mathrm{{L}}}_{H}% \preccurlyeq\lambda\boldsymbol{\mathrm{{L}}}_{G}$ , then $\vec{G}_{3}=\frac{1}{2}\beta(\lambda+1)\boldsymbol{\mathrm{{L}}}_{H}+\vec{H}_{2}$ satisfies that $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{3}}^{\dagger}$ is a $(1-\frac{2}{\lambda+1})$ -approximate pseudoinverse of $\vec{\boldsymbol{\mathrm{{L}}}}_{\vec{G}_{2}}$ with respect to $\boldsymbol{\mathrm{{L}}}_{G_{3}}$ and $\boldsymbol{\mathrm{{L}}}_{G_{2}}\preccurlyeq\boldsymbol{\mathrm{{L}}}_{G_{3}}% \preccurlyeq\frac{1}{2}\lambda(\lambda+1)\cdot\boldsymbol{\mathrm{{L}}}_{G_{2}}$ .

5.2 Dynamic reductions to pruned almost uniform degree expanders

We will consider a variant of expanders where the minimum degree is guaranteed to be close to the average degree. We say that an graph $G=(V,E,\boldsymbol{\mathrm{w}})$ is ( $\phi,\gamma$ )-uniform degree expander if $G$ is a $\phi$ -expander and and that $\frac{\max_{v\in V}\boldsymbol{\mathrm{d}}_{v}}{\min_{v\in V}\boldsymbol{% \mathrm{d}}_{v}}\leq\gamma^{-1}$ , where we denote $\boldsymbol{\mathrm{d}}_{v}=\sum_{e\in E|e\ni v}\boldsymbol{\mathrm{w}}_{e}$ as the weighted degree of $v$ . Recall that we assume the subgraphs in a decomposition contain the entire set of edges.

An uniform degree expander decomposition of a graph is defined similarly to Definition 16 but with a few additional requirments on the degrees. For each subgraph $\vec{G}_{i}$ , it is associated with a graph $\vec{G}_{i}^{\prime}$ supported on the vertices of $\vec{G}_{i}$ and extra sets of vertices $\{Y_{v,i}\}$ for $v\in V(\vec{G}_{i})$ . The graph $\vec{G}_{i}^{\prime}$ is required to be a $(\phi,\gamma)$ -uniform degree expander satisfing that contracting each $Y_{v,i}$ in $\vec{G}_{i}^{\prime}$ gives $\vec{G}_{i}$ .

Informally speaking, Theorem 5.8 in [11] provide a similar algorithm to Proposition 18 where an uniform degree expander decomposition of a weighted dynamic graph can be maintained efficiently where each expander undergoes only decremental updates. In the full version, we provide a slight modification for directed graphs and with edge weight bucketing.

We now recall the reduction to decremental algorithm on uniform degree expanders by [11] using this dynamic uniform degree expander decomposition algorithm from above. The version we present here is an informal version of Theorem 5.2 in [11] with a slight generalization: we remove the perturbation condition and allows for directed graphs.

Lemma 41 (Informal blackbox adaptive reduction with uniform degree promise).

Assume $\mathcal{H}$ is a graph sparsification problem that satisfies the union and contraction property, and there is a decremental algorithm $\mathcal{A}$ for $\mathcal{H}$ on (directed) graphs with edge weights ratio at most $2$ and satisfying that their corresponding undirected graph is a uniform degree expander.

Then, there exists a fully dynamic algorithm $\mathcal{B}$ for $\mathcal{H}$ on weighted (directed) graphs such that given a dynamic weighted simple directed graph $\vec{G}$ maintains an $\varepsilon$ -approximate sparsifier of essentially the same size with essentially the same amortized update time as $\mathcal{A}$ . Moreover, $\mathcal{B}$ works against an adaptive adversary if $\mathcal{A}$ supports adaptive edge updates.

5.3 Adaptive degree preserving sparsifications

In this section, we provide our guarantees for dynamic sparsification from $\vec{G}_{i}$ to $\vec{G}_{i+1}$ .

Theorem 42 gives dynamic sparsification from $\vec{G}_{2}$ to $\vec{G}_{3}$ , which, by Lemma 40, reduces to the sparsification of the undirected graph $G=\textup{und}(\vec{G})$ against an adaptive adversary.

Theorem 42.

There is a fully dynamic algorithm that given as input a weighted undirected graph $G=(V,E,\boldsymbol{\mathrm{w}})$ with bounded weight ratio $W$ at all time undergoing adaptive edge insertions and deletions, maintain explicitly a graph $\vec{H}$ on vertices $V\cup X$ with $X$ disjoint from $V$ . The Schur complement $S=\operatorname{\mathtt{Sc}}(\vec{H},V)$ is an undirected graph and satisfies with high probability that $S$ is $O(\log^{12}n)$ -degree preserving spectral approximation of $G$ . The graph $\vec{H}$ has size $\widetilde{O}(n\log W)$ and extra number of vertices $|X|\leq O(n\log^{3}n\log W)$ . The algorithm has preprocessing time $\widetilde{O}(m)$ and amortized update time $\widetilde{O}(1)$ .

For sparsification from $\vec{G}_{1}$ to $\vec{G}_{2}$ , by Lemma 38, it suffices to produce a $\varepsilon$ -degree preserving spectral sparsification $\vec{H}$ of $\vec{G}$ with respect to $\boldsymbol{\mathrm{{L}}}_{G^{(\beta)}}$ . The exact statement of our guarantees is presented in Lemma 43.

Lemma 43.

Let $\vec{G}=(V,E,\boldsymbol{\mathrm{w}})$ be a dynamic weighted directed graph undergoing adaptive edge updates. There is a deterministic dynamic algorithm that for $\varepsilon\in(0,1)$ , if $\beta\geq\Omega(\varepsilon^{-1}\log^{4}n)$ , it maintains explicitly a weighted directed graph $\vec{H}=(V\cup X,E_{\vec{H}},\boldsymbol{\mathrm{w}}_{vH})$ satisfying that for Schur complement $\vec{S}=\operatorname{\mathtt{Sc}}(\vec{H},V)$ $\vec{G}^{\prime}=\beta\cdot G\cup\vec{S}$ is a $\varepsilon$ -degree preserving directed spectral sparsifier of $\vec{G}^{(\beta)}$ , where $G=\textup{und}(\vec{G})$ . The graph $\vec{H}$ has size $\widetilde{O}(n\log W)$ and extra number of vertices $|X|\leq O(n\log^{3}n\log W)$ . The algorithm has preprocessing time $\widetilde{O}(m)$ and amortized update time $\widetilde{O}(1)$ .

Our algorithm in Theorem 8 maintains (a) a copy of the algorithm from Lemma 43 for sparsification from $\vec{G}_{1}$ to $\vec{G}_{2}$ , and (b) a copy of the algorithm from Theorem 42 for sparsification from $\vec{G}_{2}$ to $\vec{G}_{3}$ with the sparsifier scaled appropriately. Note that (a) maintains a graph $\vec{H}_{2}$ on $V\cup X$ and (b) maintain a graph $\vec{H}_{3}$ on $V\cup X^{\prime}$ for some subset $X^{\prime}$ disjoint from $X$ . By the disjointness, we have the following equivalence in the Schur complement,

\operatorname{\mathtt{Sc}}(\vec{G}_{3},V)=\operatorname{\mathtt{Sc}}(\vec{H}_{% 3}\cup\vec{H}_{2},V)=\operatorname{\mathtt{Sc}}(\vec{H}_{3},V)\cup% \operatorname{\mathtt{Sc}}(\vec{H}_{2},V).

Then, the union property (Lemma 11) then ensures the Schur complement $\operatorname{\mathtt{Sc}}(\vec{H}_{3}\cup\vec{H}_{2},H)$ is a degree preserving spectral approximation to $\vec{G}_{2}$ . Theorem 8 follows by picking appropriate parameters in Theorem 42 and Lemma 43.

To prove Theorem 42, we use the observation that a degree preserving undirected cut sparsifier of an expander is a good spectral to the expander as well (Lemma 45). This observation allows to utilize an adaptive algorithm for cut sparsification from [11] on decremental uniform degree expanders.

Definition 44 (Undirected cut approximation, multiplicative).

$H=(V,E_{H},\boldsymbol{\mathrm{w}}_{H})$ is a $\gamma$ -cut approximation of $G=(V,E,\boldsymbol{\mathrm{w}})$ if for all non-trivial ut $(U,V\setminus U)$ , it satisfies that

\boldsymbol{\mathrm{w}}(U,V\setminus U)\leq\boldsymbol{\mathrm{w}}_{H}(U,V% \setminus U)\leq\gamma\cdot\boldsymbol{\mathrm{w}}(U,V\setminus U).

Lemma 45 ([17, 11]).

Let $G, H$ be weighted undirected graphs with the same set of vertices and satisfying $\boldsymbol{\mathrm{d}}_{G}=\boldsymbol{\mathrm{d}}_{H}$ . If both $G, H$ are $\phi$ -expanders for $\phi\in(0,1]$ , then

\frac{\phi^{2}}{4}\boldsymbol{\mathrm{{L}}}_{G}\preccurlyeq\boldsymbol{\mathrm% {{L}}}_{H}\preccurlyeq\frac{4}{\phi^{2}}\boldsymbol{\mathrm{{L}}}_{G}.

We observe that a degree preserving spectral sparsifier of an almost uniform degree expander is easy to compute using cut sparsifiers and our patching scheme in Lemma 46. Note that our returned graph $\vec{H}$ on vertices $V\cup X$ is instead directed. This is not a problem: (1) our overall sparsifier $\vec{G}_{3}$ is ultimately a directed graph, and (2) the Schur complement $S=\operatorname{\mathtt{Sc}}(\vec{H},V)$ back onto the original set of vertices is an undirected graph. We further notice that Lemma 46 require specifically for the graph $G$ to be a bipartite graph. This is an important assumption to ensure our star patching does not generate self-loops after “unlifting” the graph. See Section 3.6 for the exact reduction.

Lemma 46.

Let weighted bipartite undirected graph $G=(C\cup R,E,\boldsymbol{\mathrm{w}})$ be a $\phi$ -expander. If $\widetilde{G}$ is a $\gamma$ -cut approximation of $G$ , then there is a deterministic algorithm that computes in time $O(m_{G}+m_{\widetilde{G}}+n\log n)$ a directed graph $\vec{H}$ on vertices $V\cup\{x,y\}$ for $V=C\cup R$ such that the Schur complement $S=\operatorname{\mathtt{Sc}}(H,V)$ is an undirected graph that satisfies $\boldsymbol{\mathrm{d}}_{S}=\boldsymbol{\mathrm{d}}_{G}$ , and $\frac{4\gamma^{2}}{\phi^{2}}\cdot S$ is a $\frac{16\gamma^{4}}{\phi^{4}}$ -spectral approximation of $G$ . The graph $H$ has size $m_{H}=O(m_{\widetilde{G}}+n)$ ,

We can now apply a decremental cut sparsification algorithm from [11] for spectral sparsification. Remark that the following Lemma 47 has a slight modification to allow for edge weights to be within a factor of 2, instead of uniform. Theorem 42 is then a direct consequence when combined with Lemma 46.

Lemma 47 (Decremental adaptive cut sparsifier, Theorem 9.5 [11]).

Let $G=(V,E,\boldsymbol{\mathrm{w}})$ be a decremental weighted graph undergoing adaptive edge deletions that satisfies $L\leq\boldsymbol{\mathrm{w}}_{e}\leq 2L$ for all $e$ and $\Delta_{\textup{max}}\geq\boldsymbol{\mathrm{d}}_{v}\geq\Delta_{\textup{min}}% \geq\frac{80\log n}{\phi}$ for some fixed $\phi,L$ , where $\Delta_{\textup{max}}$ is the maximum weighted degree in the initial graph $G$ and $\Delta_{\textup{min}}$ is a degree lowerbound. Then, there is an algorithm that maintains a reweighted subgraph $H$ of $G$ such that $m_{H}=\widetilde{O}\left(n(\frac{\Delta_{\textup{max}}}{\phi\Delta_{\textup{% min}}})^{2}\right)$ and at any stage where $H$ has $\min_{v\in V}\boldsymbol{\mathrm{d}}_{v}\geq\Delta_{\textup{min}}$ and $\phi(H)\geq\phi$ on non-trivial vertices, $H$ is a $O(\log n)$ -approximate cut sparsifier of $H$ with high probability. The algorithm has preprocessing time $O(m)$ and worst-case update time $\widetilde{O}\left((\frac{\Delta_{\textup{max}}}{\phi\Delta_{\textup{min}}})^{% 3}\right)$ .

Consider sparsification from $\vec{G}_{1}$ to $\vec{G}_{2}$ . Similar to the undirected sparsification, a directed graph $\vec{H}$ can be computed using a star patching for expanders. We again considers a bipartite graph with “disjoint” vertices to avoid self-loops when eliminating the extra vertices. Lemma 43 can then be proven straightforwardly using Lemma 48.

Lemma 48.

Let $\vec{G}=(C\cup R,E,\boldsymbol{\mathrm{w}})$ be a weighted bipartite directed graph with $E\subseteq C\times R$ so that $G=\textup{und}(\vec{G})$ is a $\phi$ -expander. There is a deterministic algorithm that given $\varepsilon\in(0,1)$ , and $\beta$ satisfying $\beta\geq 2\varepsilon^{-1}\phi^{-2}$ , returns in time $O(m+n\log n)$ a graph $\vec{H}$ on vertices $C\cup R\cup\{x\}$ of size $O(n)$ such that for $\vec{G}^{\prime}=\beta\cdot G\cup\operatorname{\mathtt{Sc}}(\vec{H},C\cup R)$ is a $\varepsilon$ -degree preserving directed spectral sparsifier of $\vec{G}^{(\beta)}$ .

References

[1] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 335–344, 2016. doi:10.1109/FOCS.2016.44.
[2] Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander decomposition with fewer inter-cluster edges using a spectral cut player. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 9:1–9:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.9.
[3] AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, and Aaron Sidford. Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications, pages 1387–1404. SIAM, 2019. doi:10.1137/1.9781611975482.85.
[4] AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil P. Vadhan. High-precision estimation of random walks in small space. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1295–1306. IEEE, 2020. doi:10.1109/FOCS46700.2020.00123.
[5] AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, and Salil P. Vadhan. Singular value approximation and sparsifying random walks on directed graphs. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 846–854. IEEE, 2023. doi:10.1109/FOCS57990.2023.00054.
[6] Giorgio Ausiello, Paolo Franciosa, and Giuseppe Italiano. Small stretch spanners on dynamic graphs. Journal of Graph Algorithms and Applications, 10(2):365–385, 2006. doi:10.7155/JGAA.00133.
[7] Nikhil Bansal, Haotian Jiang, and Raghu Meka. Resolving matrix spencer conjecture up to poly-logarithmic rank. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1814–1819. ACM, 2023. doi:10.1145/3564246.3585103.
[8] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4), October 2012. doi:10.1145/2344422.2344425.
[9] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 47–55. Association for Computing Machinery, 1996. doi:10.1145/237814.237827.
[10] Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Trans. Algorithms, 17(4), October 2021. doi:10.1145/3469833.
[11] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2022.20.
[12] Karl Bringmann and Konstantinos Panagiotou. Efficient sampling methods for discrete distributions. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 133–144, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. doi:10.1007/978-3-642-31594-7_12.
[13] Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun. Sparsification of Directed Graphs via Cut Balance. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1–45:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.45.
[14] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022. doi:10.1109/FOCS54457.2022.00064.
[15] Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, and Jason Zhang. Tight lower bounds for directed cut sparsification and distributed min-cut. Proc. ACM Manag. Data, 2(2), May 2024. doi:10.1145/3651148.
[16] Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 361–372, 2018. doi:10.1109/FOCS.2018.00042.
[17] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1158–1167, 2020. doi:10.1109/FOCS46700.2020.00111.
[18] Julia Chuzhoy and Merav Parter. Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition, pages 785–823. SIAM, 2025. doi:10.1137/1.9781611978322.23.
[19] Michael B Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B Rao, and Aaron Sidford. Solving directed laplacian systems in nearly-linear time through sparse lu factorizations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 898–909. IEEE, 2018. doi:10.1109/FOCS.2018.00089.
[20] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 410–419, 2017. doi:10.1145/3055399.3055463.
[21] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 583–592. IEEE, 2016. doi:10.1109/FOCS.2016.69.
[22] Luc Devroye. Chapter 4 nonuniform random variate generation. In Shane G. Henderson and Barry L. Nelson, editors, Simulation, volume 13 of Handbooks in Operations Research and Management Science, pages 83–121. Elsevier, 2006. doi:10.1016/S0927-0507(06)13004-2.
[23] Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2), March 2011. doi:10.1145/1921659.1921666.
[24] Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford. Routing under balance. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 598–611, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2897518.2897654.
[25] Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 377–388, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3313276.3316381.
[26] Sebastian Forster, Gramoz Goranci, Yang P Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. Minor sparsifiers and the distributed laplacian paradigm. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 989–999. IEEE, 2021. doi:10.1109/FOCS52979.2021.00099.
[27] Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 71–80, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1993636.1993647.
[28] David Gibb, Bruce Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space, 2015. arXiv:1509.06464.
[29] Gramoz Goranci, Monika Henzinger, Harald Räcke, and A. R. Sricharan. Incremental Approximate Maximum Flow via Residual Graph Sparsification. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 91:1–91:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.91.
[30] Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015, pages 742–753, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. doi:10.1007/978-3-662-48350-3_62.
[31] Arun Jambulapati, Victor Reis, and Kevin Tian. Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory, pages 5169–5208. SIAM, 2024. doi:10.1137/1.9781611977912.186.
[32] Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, and Yibin Zhao. Eulerian Graph Sparsification by Effective Resistance Decomposition, pages 1607–1650. SIAM, 2025. doi:10.1137/1.9781611978322.50.
[33] Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time, pages 1131–1142. SIAM, 2013. doi:10.1137/1.9781611973105.81.
[34] David R. Karger and Matthew S. Levine. Fast augmenting paths by random sampling from residual graphs. SIAM Journal on Computing, 44(2):320–339, 2015. doi:10.1137/070705994.
[35] Donald E. Knuth. The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms. Addison-Wesley Longman Publishing Co., Inc., USA, 1997.
[36] Ioannis Koutis and Shen Chen Xu. Simple parallel and distributed algorithms for spectral graph sparsification. ACM Trans. Parallel Comput., 3(2), 2016. doi:10.1145/2948062.
[37] Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg. Derandomizing directed random walks in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 407–418, 2022. doi:10.1109/FOCS54457.2022.00046.
[38] Lap Chi Lau, Robert Wang, and Hong Zhou. Spectral Sparsification by Deterministic Discrepancy Walk, pages 315–340. SIAM, 2025. doi:10.1137/1.9781611978315.24.
[39] Huan Li and Aaron Schild. Spectral subspace sparsification. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 385–396. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00044.
[40] Yang P Liu, Sushant Sachdeva, and Zejun Yu. Short cycles via low-diameter decompositions. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2602–2615. SIAM, 2019. doi:10.1137/1.9781611975482.161.
[41] Merav Parter and Eylon Yogev. Optimal Short Cycle Decomposition in Almost Linear Time. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 89:1–89:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.89.
[42] Richard Peng and Zhuoqing Song. Sparsified block elimination for directed laplacians. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 557–567. ACM, 2022. doi:10.1145/3519935.3520053.
[43] Lucas Pesenti and Adrian Vladu. Discrepancy Minimization via Regularization, pages 1734–1758. SIAM, 2023. doi:10.1137/1.9781611977554.ch66.
[44] Sushant Sachdeva, Anvith Thudi, and Yibin Zhao. Better Sparsifiers for Directed Eulerian Graphs. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 119:1–119:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.119.
[45] Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2616–2635. SIAM, 2019. doi:10.1137/1.9781611975482.162.
[46] Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011. doi:10.1137/080734029.
[47] Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 503–514, 2023. doi:10.1109/FOCS57990.2023.00037.
[48] Yibin Zhao. Fully dynamic spectral and cut sparsifiers for directed graphs, 2025. doi:10.48550/arXiv.2507.19632.

[bib.bib1] [1] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 335–344, 2016. doi:10.1109/FOCS.2016.44.

[bib.bib2] [2] Daniel Agassy, Dani Dorfman, and Haim Kaplan. Expander decomposition with fewer inter-cluster edges using a spectral cut player. In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, July 10-14, 2023, Paderborn, Germany, volume 261 of LIPIcs, pages 9:1–9:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ICALP.2023.9.

[bib.bib3] [3] AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, and Aaron Sidford. Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications, pages 1387–1404. SIAM, 2019. doi:10.1137/1.9781611975482.85.

[bib.bib4] [4] AmirMahdi Ahmadinejad, Jonathan A. Kelner, Jack Murtagh, John Peebles, Aaron Sidford, and Salil P. Vadhan. High-precision estimation of random walks in small space. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 1295–1306. IEEE, 2020. doi:10.1109/FOCS46700.2020.00123.

[bib.bib5] [5] AmirMahdi Ahmadinejad, John Peebles, Edward Pyne, Aaron Sidford, and Salil P. Vadhan. Singular value approximation and sparsifying random walks on directed graphs. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, pages 846–854. IEEE, 2023. doi:10.1109/FOCS57990.2023.00054.

[bib.bib6] [6] Giorgio Ausiello, Paolo Franciosa, and Giuseppe Italiano. Small stretch spanners on dynamic graphs. Journal of Graph Algorithms and Applications, 10(2):365–385, 2006. doi:10.7155/JGAA.00133.

[bib.bib7] [7] Nikhil Bansal, Haotian Jiang, and Raghu Meka. Resolving matrix spencer conjecture up to poly-logarithmic rank. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, pages 1814–1819. ACM, 2023. doi:10.1145/3564246.3585103.

[bib.bib8] [8] Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4), October 2012. doi:10.1145/2344422.2344425.

[bib.bib9] [9] András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in Õ(n2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’96, pages 47–55. Association for Computing Machinery, 1996. doi:10.1145/237814.237827.

[bib.bib10] [10] Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. ACM Trans. Algorithms, 17(4), October 2021. doi:10.1145/3469833.

[bib.bib11] [11] Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:20, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2022.20.

[bib.bib12] [12] Karl Bringmann and Konstantinos Panagiotou. Efficient sampling methods for discrete distributions. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 133–144, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. doi:10.1007/978-3-642-31594-7_12.

[bib.bib13] [13] Ruoxu Cen, Yu Cheng, Debmalya Panigrahi, and Kevin Sun. Sparsification of Directed Graphs via Cut Balance. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 45:1–45:21, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2021.45.

[bib.bib14] [14] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623, 2022. doi:10.1109/FOCS54457.2022.00064.

[bib.bib15] [15] Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, and Jason Zhang. Tight lower bounds for directed cut sparsification and distributed min-cut. Proc. ACM Manag. Data, 2(2), May 2024. doi:10.1145/3651148.

[bib.bib16] [16] Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang. Graph sparsification, spectral sketches, and faster resistance computation, via short cycle decompositions. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 361–372, 2018. doi:10.1109/FOCS.2018.00042.

[bib.bib17] [17] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1158–1167, 2020. doi:10.1109/FOCS46700.2020.00111.

[bib.bib18] [18] Julia Chuzhoy and Merav Parter. Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition, pages 785–823. SIAM, 2025. doi:10.1137/1.9781611978322.23.

[bib.bib19] [19] Michael B Cohen, Jonathan Kelner, Rasmus Kyng, John Peebles, Richard Peng, Anup B Rao, and Aaron Sidford. Solving directed laplacian systems in nearly-linear time through sparse lu factorizations. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 898–909. IEEE, 2018. doi:10.1109/FOCS.2018.00089.

[bib.bib20] [20] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Anup B Rao, Aaron Sidford, and Adrian Vladu. Almost-linear-time algorithms for markov chains and new spectral primitives for directed graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 410–419, 2017. doi:10.1145/3055399.3055463.

[bib.bib21] [21] Michael B Cohen, Jonathan Kelner, John Peebles, Richard Peng, Aaron Sidford, and Adrian Vladu. Faster algorithms for computing the stationary distribution, simulating random walks, and more. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 583–592. IEEE, 2016. doi:10.1109/FOCS.2016.69.

[bib.bib22] [22] Luc Devroye. Chapter 4 nonuniform random variate generation. In Shane G. Henderson and Barry L. Nelson, editors, Simulation, volume 13 of Handbooks in Operations Research and Management Science, pages 83–121. Elsevier, 2006. doi:10.1016/S0927-0507(06)13004-2.

[bib.bib23] [23] Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2), March 2011. doi:10.1145/1921659.1921666.

[bib.bib24] [24] Alina Ene, Gary Miller, Jakub Pachocki, and Aaron Sidford. Routing under balance. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC ’16, pages 598–611, New York, NY, USA, 2016. Association for Computing Machinery. doi:10.1145/2897518.2897654.

[bib.bib25] [25] Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 377–388, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145/3313276.3316381.

[bib.bib26] [26] Sebastian Forster, Gramoz Goranci, Yang P Liu, Richard Peng, Xiaorui Sun, and Mingquan Ye. Minor sparsifiers and the distributed laplacian paradigm. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 989–999. IEEE, 2021. doi:10.1109/FOCS52979.2021.00099.

[bib.bib27] [27] Wai Shing Fung, Ramesh Hariharan, Nicholas J.A. Harvey, and Debmalya Panigrahi. A general framework for graph sparsification. In Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC ’11, pages 71–80, New York, NY, USA, 2011. Association for Computing Machinery. doi:10.1145/1993636.1993647.

[bib.bib28] [28] David Gibb, Bruce Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space, 2015. arXiv:1509.06464.

[bib.bib29] [29] Gramoz Goranci, Monika Henzinger, Harald Räcke, and A. R. Sricharan. Incremental Approximate Maximum Flow via Residual Graph Sparsification. In Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, editors, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of Leibniz International Proceedings in Informatics (LIPIcs), pages 91:1–91:20, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2025.91.

[bib.bib30] [30] Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Nikhil Bansal and Irene Finocchi, editors, Algorithms - ESA 2015, pages 742–753, Berlin, Heidelberg, 2015. Springer Berlin Heidelberg. doi:10.1007/978-3-662-48350-3_62.

[bib.bib31] [31] Arun Jambulapati, Victor Reis, and Kevin Tian. Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory, pages 5169–5208. SIAM, 2024. doi:10.1137/1.9781611977912.186.

[bib.bib32] [32] Arun Jambulapati, Sushant Sachdeva, Aaron Sidford, Kevin Tian, and Yibin Zhao. Eulerian Graph Sparsification by Effective Resistance Decomposition, pages 1607–1650. SIAM, 2025. doi:10.1137/1.9781611978322.50.

[bib.bib33] [33] Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time, pages 1131–1142. SIAM, 2013. doi:10.1137/1.9781611973105.81.

[bib.bib34] [34] David R. Karger and Matthew S. Levine. Fast augmenting paths by random sampling from residual graphs. SIAM Journal on Computing, 44(2):320–339, 2015. doi:10.1137/070705994.

[bib.bib35] [35] Donald E. Knuth. The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms. Addison-Wesley Longman Publishing Co., Inc., USA, 1997.

[bib.bib36] [36] Ioannis Koutis and Shen Chen Xu. Simple parallel and distributed algorithms for spectral graph sparsification. ACM Trans. Parallel Comput., 3(2), 2016. doi:10.1145/2948062.

[bib.bib37] [37] Rasmus Kyng, Simon Meierhans, and Maximilian Probst Gutenberg. Derandomizing directed random walks in almost-linear time. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 407–418, 2022. doi:10.1109/FOCS54457.2022.00046.

[bib.bib38] [38] Lap Chi Lau, Robert Wang, and Hong Zhou. Spectral Sparsification by Deterministic Discrepancy Walk, pages 315–340. SIAM, 2025. doi:10.1137/1.9781611978315.24.

[bib.bib39] [39] Huan Li and Aaron Schild. Spectral subspace sparsification. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 385–396. IEEE Computer Society, 2018. doi:10.1109/FOCS.2018.00044.

[bib.bib40] [40] Yang P Liu, Sushant Sachdeva, and Zejun Yu. Short cycles via low-diameter decompositions. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2602–2615. SIAM, 2019. doi:10.1137/1.9781611975482.161.

[bib.bib41] [41] Merav Parter and Eylon Yogev. Optimal Short Cycle Decomposition in Almost Linear Time. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 89:1–89:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ICALP.2019.89.

[bib.bib42] [42] Richard Peng and Zhuoqing Song. Sparsified block elimination for directed laplacians. In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 557–567. ACM, 2022. doi:10.1145/3519935.3520053.

[bib.bib43] [43] Lucas Pesenti and Adrian Vladu. Discrepancy Minimization via Regularization, pages 1734–1758. SIAM, 2023. doi:10.1137/1.9781611977554.ch66.

[bib.bib44] [44] Sushant Sachdeva, Anvith Thudi, and Yibin Zhao. Better Sparsifiers for Directed Eulerian Graphs. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 119:1–119:20, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.119.

[bib.bib45] [45] Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pages 2616–2635. SIAM, 2019. doi:10.1137/1.9781611975482.162.

[bib.bib46] [46] Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011. doi:10.1137/080734029.

[bib.bib47] [47] Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, and Aaron Sidford. A deterministic almost-linear time algorithm for minimum-cost flow. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 503–514, 2023. doi:10.1109/FOCS57990.2023.00037.

[bib.bib48] [48] Yibin Zhao. Fully dynamic spectral and cut sparsifiers for directed graphs, 2025. doi:10.48550/arXiv.2507.19632.

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs

Abstract

Keywords and phrases:

Category:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Definition 1 (β-balanced directed cut approximation).

Definition 2 (Degree balance preserving directed spectral approximation).

1.1 Our results

Theorem 3 (Explicit dynamic directed spectral sparsifier).

Corollary 4 (Dynamic RCDD Z-matrix solver).

Theorem 5 (Dynamic β-balanced cut sparsifier).

Theorem 6 (Improved static β-balanced cut sparsifier).

Definition 7 (Approximate pseudoinverse, [21]).

Theorem 8 (Adaptive directed spectral sparsification quadruple).

1.2 Related works

Static directed graph sparsification

Dynamic graph sparsification

2 Preliminaries

Vectors and Matrices

Graphs

Graph matrices

Cut, Conductance and Expanders

Definition 9.

3 A Fully Dynamic Directed Spectral Sparsifier

3.1 Properties of degree balance preserving directed spectral sparsifiers

Lemma 10.

Lemma 11 (Union property).

Lemma 12 (Contraction property).

Lemma 13.

3.2 Bipartitle lifts

Lemma 14.

Lemma 15.

3.3 Reduction to decremental sparsifier on expanders

Definition 16 (Expander decomposition).

Lemma 17 (Expander pruning).

Proposition 18 (Dynamic expander decomposition).

Lemma 19 (Informal blackbox reduction with dynamic expander decomposition).

3.4 Patching by directed star graphs

Lemma 20 (Star patching).

3.5 A simple decremental algorithm on expanders

Lemma 21.

Lemma 22.

Lemma 23.

3.6 Degree preserving directed spectral sparsification

Theorem 24 (Theorem 3, degree preserving).

4 A Fully Dynamic Balanced Directed Cut Sparsifier

Definition 25 (Edge connectivity).

Lemma 26.

Theorem 27.

Lemma 28 (Union property).

4.1 Balanced directed cut sparsifiers via edge connectivity

Proposition 29.

Definition 30.

Theorem 31 (Generalized cut projection counts, [27]).

Lemma 32.

4.2 Dynamic directed cut sparsification

Lemma 33.

5 Directed Spectral Sparsification Against an Adaptive Adversary via Partial Symmetrization

Definition 34 (Generalized partial symmetrization, [37]).

Lemma 35 (Preconditioned Iterations, Lemma 4.4 in [20]).

Definition 36 (Sparsification quadruple, [37]).

5.1 Sparsification quadruples

Lemma 37 (Lemma 4.6, [37]).

Lemma 38.

Definition 39 (Undirected spectral approximation, multiplicative).

Lemma 40.

5.2 Dynamic reductions to pruned almost uniform degree expanders

Lemma 41 (Informal blackbox adaptive reduction with uniform degree promise).

5.3 Adaptive degree preserving sparsifications

Theorem 42.

Lemma 43.

Definition 44 (Undirected cut approximation, multiplicative).

Definition 1 ( $\beta$ -balanced directed cut approximation).

Theorem 5 (Dynamic $\beta$ -balanced cut sparsifier).

Theorem 6 (Improved static $\beta$ -balanced cut sparsifier).