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 Ȏ(n log 2 n•ε -2 )-edge ε-approximate Eulerian sparsifier with high probability in Ȏ(m log 3 n) time (where Ȏ(•) hides polyloglog(n) factors). Due to a reduction from STOC '22], this yields an Ȏ(m log 3 n + n log 6 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 log 8 n + n log 23 n). We also give a polynomial-time algorithm that computes O(min

Finally, we show that our techniques extend to yield the first O(m•polylog(n)) time algorithm for computing O(nε -1 •polylog(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.