New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Authors:
- 1 November 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 910-928
Abstract
A sparsifier of a graph G (Benczú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 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. We study a weaker notion of sparsification 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 sparsifiers for every graph, and our sparsifiers have a near-optimal number of edges O(ε^-2 npolylog (1/ε)). We also provide a deterministic polynomial time construction that constructs sparsifiers with a weaker property having the optimal number of edges O(ε^-2 n). Our constructions also satisfy a spectral version of the “additive sparsification'' property. Notions of sparsification have also been studied for hypergraphs. Our construction of “additive sparsifiers'' with O_ε (n) edges also works for hypergraphs, and provides the first non-trivial notion of sparsification 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 sparsifiers, according to the standard definition, with poly (ε^-1, r) n log n hyperedges, improving over the previous spectral construction (Soma and Yoshida) that used Õ(n^3) hyperedges even for constant r and ε.Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Interlacing families II: Mixed characteristic polynomials and the Kadison--Singer problemAnnals of Mathematics, 2015
- Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates2015
- An Introduction to Matrix Concentration InequalitiesFoundations and Trends in Machine Learning, 2015
- Sketching Cuts in Graphs and Hypergraphs2015
- Twice-Ramanujan SparsifiersSIAM Journal on Computing, 2012
- New Constructive Aspects of the Lovász Local LemmaJournal of the ACM, 2011
- Graph Sparsification by Effective ResistancesSIAM Journal on Computing, 2011
- Lifts, Discrepancy and Nearly Optimal Spectral Gap*Combinatorica, 2006
- Splitting an Expander GraphJournal of Algorithms, 1999
- Approximating s-t minimum cuts in Õ(n2) time1996