Cut Sparsification and Succinct Representation of Submodular Hypergraphs
share
In cut sparsification, all cuts of a hypergraph H=(V,E,w) are approximated within 1±ϵ factor by a small hypergraph H'. This widely applied method was generalized recently to a setting where the cost of cutting each e∈ E is provided by a splitting function, g_e: 2^e→ℝ_+. This generalization is called a submodular hypergraph when the functions {g_e}_e∈ E are submodular, and it arises in machine learning, combinatorial optimization, and algorithmic game theory. Previous work focused on the setting where H' is a reweighted sub-hypergraph of H, and measured size by the number of hyperedges in H'. We study such sparsification, and also a more general notion of representing H succinctly, where size is measured in bits. In the sparsification setting, where size is the number of hyperedges, we present three results: (i) all submodular hypergraphs admit sparsifiers of size polynomial in n=|V|; (ii) monotone-submodular hypergraphs admit sparsifiers of size O(ϵ^-2 n^3); and (iii) we propose a new parameter, called spread, to obtain even smaller sparsifiers in some cases. In the succinct-representation setting, we show that a natural family of splitting functions admits a succinct representation of much smaller size than via reweighted subgraphs (almost by factor n). This large gap is surprising because for graphs, the most succinct representation is attained by reweighted subgraphs. Along the way, we introduce the notion of deformation, where g_e is decomposed into a sum of functions of small description, and we provide upper and lower bounds for deformation of common splitting functions.
READ FULL TEXT