Eulerian Graph Sparsification by Effective Resistance Decomposition

We provide an algorithm that, given an n-vertex m-edge Eulerian graph with polynomially bounded weights, computes an O (n^2 n ^-2) -edge -approximate Eulerian sparsifier with high probability in O (m³ n) time (where O () hides polyloglog (n) factors). Due to a reduction from Peng-Song, STOC '22, this yields an O (m³ n + n⁶ n) -time algorithm for solving n-vertex m-edge Eulerian Laplacian systems with polynomially-bounded weights with high probability, improving upon the previous state-of-the-art runtime of (m⁸ n + n^23 n). We also give a polynomial-time algorithm that computes O ( (n n ^-2 + n^5/3 n ^-4/3, n^3/2 n ^-2) ) -edge sparsifiers, improving the best such sparsity bound of O (n² n ^-2 + n^8/3 n ^-4/3) Sachdeva-Thudi-Zhao, ICALP '24. Finally, we show that our techniques extend to yield the first O (m (n) ) time algorithm for computing O (n^-1 (n) ) -edge graphical spectral sketches, as well as a natural Eulerian generalization we introduce. In contrast to prior Eulerian graph sparsification algorithms which used either short cycle or expander decompositions, our algorithms use a simple efficient effective resistance decomposition scheme we introduce. Our algorithms apply a natural sampling scheme and electrical routing (to achieve degree balance) to such decompositions. Our analysis leverages new asymmetric variance bounds specialized to Eulerian Laplacians and tools from discrepancy theory.