New Notions and Constructions of Sparsification for Graphs and Hypergraphs

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs in which different edges have different weights. Even for graphs that admit unweighted sparsifiers (that is, sparsifiers in which all the edge weights are equal to the same scaling factor), there are no known polynomial time algorithms that find such unweighted sparsifiers.