New Notions and Constructions of Sparsification for Graphs and Hypergraphs
A sparsiﬁer of a graph G (Benczu´r and Karger; Spielman and Teng) is a sparse weighted subgraph ˜ G that approximately retains the same cut structure of G. For general graphs, non-trivial sparsiﬁcation is possible only by using weighted graphs in which diﬀerent edges have diﬀerent weights. Even for graphs that admit unweighted sparsiﬁers (that is, sparsiﬁers in which all the edge weights are equal to the same scaling factor), there are no known polynomial time algorithms that ﬁnd such unweighted sparsiﬁers. We study a weaker notion of sparsiﬁcation suggested by Oveis Gharan, in which the number of cut edges in each cut (S, ¯ S) is not approximated within a multiplicative factor (1 + ǫ), but is, instead, approximated up to an additive term bounded by ǫ times d · |S| + vol(S), where d is the average degree of the graph and vol(S) is the sum of the degrees of the vertices in S. We provide a probabilistic polynomial time construction of such sparsiﬁers for every graph, and our sparsiﬁers have a near-optimal number of edges O(ǫ−2npolylog(1/ǫ)). We also provide a deterministic polynomial time construction that constructs sparsiﬁers with a weaker property having the optimal number of edges O(ǫ−2n). Our constructions also satisfy a spectral version of the “additive sparsiﬁcation” property. Notions of sparsiﬁcation have also been studied for hypergraphs. Our construction of “additive sparsiﬁers” with Oǫ(n) edges also works for hypergraphs, and provides the ﬁrst non-trivial notion of sparsiﬁcation for hypergraphs achievable with O(n) hyperedges when ǫ and the rank r of the hyperedges are constant. Finally, we provide a new construction of spectral hypergraph sparsiﬁers, according to the standard deﬁnition, with poly(ǫ−1,r)·nlogn hyperedges, improving over the previous spectral construction (Soma and Yoshida) that used ˜ O(n3) hyperedges even for constant r and ǫ.
Bansal, N, Svensson, O, & Trevisan, L. (2019). New Notions and Constructions of Sparsification for Graphs and Hypergraphs.