DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.157

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs

Authors: Yibin Zhao

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

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(ε^{-2} ⋅ polylog(n)) and produces a sparsifier of size O(ε^{-2} n ⋅ polylog(n)). Additionally, we present an algorithm that maintains a constant-factor approximation sparsifier of size O(n ⋅ polylog(n)) against an adaptive adversary for O(polylog(n))-partially symmetrized graphs, a notion introduced in [Kyng-Meierhans-Probst Gutenberg '22]. A β-partial symmetrization of a directed graph G is the union of G and β ⋅ G, where G is the corresponding undirected graph of G. This algorithm also achieves a polylogarithmic amortized update time. Moreover, we develop a fully dynamic algorithm for maintaining a cut sparsifier for β-balanced directed graphs, where the ratio between weighted incoming and outgoing edges of any cut is at most β. This algorithm explicitly maintains a cut sparsifier of size O(ε^{-2}β n ⋅ polylog(n)) in worst-case update time O(ε^{-2}β ⋅ polylog(n)).

Cite as

Yibin Zhao. Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 157:1-157:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{zhao:LIPIcs.ICALP.2026.157,
  author =	{Zhao, Yibin},
  title =	{{Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{157:1--157:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.157},
  URN =		{urn:nbn:de:0030-drops-265468},
  doi =		{10.4230/LIPIcs.ICALP.2026.157},
  annote =	{Keywords: Dynamic graph algorithm, Spectral graph theory, Sparsifier}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2024.119

Better Sparsifiers for Directed Eulerian Graphs

Authors: Sushant Sachdeva, Anvith Thudi, and Yibin Zhao

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract

Spectral sparsification for directed Eulerian graphs is a key component in the design of fast algorithms for solving directed Laplacian linear systems. Directed Laplacian linear system solvers are crucial algorithmic primitives to fast computation of fundamental problems on random walks, such as computing stationary distributions, hitting and commute times, and personalized PageRank vectors. While spectral sparsification is well understood for undirected graphs and it is known that for every graph G, (1+ε)-sparsifiers with O(nε^{-2}) edges exist [Batson-Spielman-Srivastava, STOC '09] (which is optimal), the best known constructions of Eulerian sparsifiers require Ω(nε^{-2}log⁴ n) edges and are based on short-cycle decompositions [Chu et al., FOCS '18]. In this paper, we give improved constructions of Eulerian sparsifiers, specifically: 1) We show that for every directed Eulerian graph G→, there exists an Eulerian sparsifier with O(nε^{-2} log² n log²log n + nε^{-4/3}log^{8/3} n) edges. This result is based on combining short-cycle decompositions [Chu-Gao-Peng-Sachdeva-Sawlani-Wang, FOCS '18, SICOMP] and [Parter-Yogev, ICALP '19], with recent progress on the matrix Spencer conjecture [Bansal-Meka-Jiang, STOC '23]. 2) We give an improved analysis of the constructions based on short-cycle decompositions, giving an m^{1+δ}-time algorithm for any constant δ > 0 for constructing Eulerian sparsifiers with O(nε^{-2}log³ n) edges.

Cite as

Sushant Sachdeva, Anvith Thudi, and Yibin Zhao. Better Sparsifiers for Directed Eulerian Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 119:1-119:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sachdeva_et_al:LIPIcs.ICALP.2024.119,
  author =	{Sachdeva, Sushant and Thudi, Anvith and Zhao, Yibin},
  title =	{{Better Sparsifiers for Directed Eulerian Graphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{119:1--119:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.119},
  URN =		{urn:nbn:de:0030-drops-202628},
  doi =		{10.4230/LIPIcs.ICALP.2024.119},
  annote =	{Keywords: Graph algorithms, Linear algebra and computation, Discrepancy theory}
}

Search Results

Documents authored by Zhao, Yibin

Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs

Abstract

Cite as

Better Sparsifiers for Directed Eulerian Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message