Near-linear Size Hypergraph Cut Sparsifiers

Yu Chen, Sanjeev Khanna, Ansh Nagda

Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cu…