Cut Sparsification and Succinct Representation of Submodular Hypergraphs

In cut sparsification, all cuts of a hypergraph $H=(V,E,w)$ are approximated within $1\pm\epsilon$ factor by a small hypergraph $H'$. This widely applied method was generalized recently to a setting where the cost of cutting each $e\in E$ is provided by a splitting function, $g_e: 2^e\to\mathbb{R}_+$. This generalization is called a submodular hypergraph when the functions $\{g_e\}_{e\in 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(\epsilon^{-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.