Graph Sparsification by Effective Resistances 1: Sampling O(n log n/ε²) Edges by Effective Resistance Yields a (1±ε) Spectral Sparsifier with Probability 1/2Research Paper
Many graph algorithms run in time proportional to the number of edges. A sparsifier of a weighted graph is a graph on the same vertices with far fewer edges that approximates for the purpose at hand, so that the algorithm can be run on instead. Benczúr and Karger (1996) showed that every graph has a sparsifier with edges…