Better Sparsifiers for Directed Eulerian Graphs

• Published in: arXiv.org 2023-11
• Main Authors: Sachdeva, Sushant, Thudi, Anvith, Zhao, Yibin
• Format: Article
• Language: English
• Subjects: Algorithms; Decomposition; Graph theory; Graphs; Linear systems; Random walk
• ISSN: 2331-8422

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 distribution, hitting and commute time, and personalized PageRank vectors. While spectral sparsification is well understood for undirected graphs and it is known that for every graph \(G,\) \((1+\varepsilon)\)-sparsifiers with \(O(n\varepsilon^{-2})\) edges exist [Batson-Spielman-Srivastava, STOC '09] (which is optimal), the best known constructions of Eulerian sparsifiers require \(\Omega(n\varepsilon^{-2}\log^4 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 \(\vec{G},\) there exist an Eulerian sparsifier with \(O(n\varepsilon^{-2} \log^2 n \log^2\log n + n\varepsilon^{-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+\delta}\)-time algorithm for any constant \(\delta > 0\) for constructing Eulerian sparsifiers with \(O(n\varepsilon^{-2}\log^3 n)\) edges.