Near-Optimal Space and Time Cut Sparsification in Turnstile StreamsResearch Paper
A cut sparsifier of a weighted graph on vertices is a reweighted subgraph that approximates the weight of every cut of within a factor . Benczúr and Karger showed that every graph has one with edges, and sparsifiers have since become a basic tool for minimum cut, maximum flow, Laplacian solvers and…