Nearly Optimal Submodular Sparsification, with and without Cardinality Constraints

Abstract

We study the sparsification of decomposable submodular functions: given a sum $F(S)={\sum }_{i=1}^m{f}_i(S)$ of $m$ nonnegative submodular functions on an $n$-element ground set $[n]$ (without assuming monotonicity or symmetry), the goal is to find a sparse reweighting $\tilde{F}(S)={\sum }_{i=1}^m{w}_i{f}_i(S)$ with at most $s\ll m$ nonzero weights that preserves $F(S)$ within a $(1\pm \epsilon )$ factor across a target family of queries. For all subset queries $S\subseteq [n]$, we give a polynomial-time randomized algorithm that constructs a sparsifier of size $O(n^2\log n/{\epsilon }^2)$. This improves upon the previous best upper bound of $O(n^3/{\epsilon }^2)$ by Kenneth and Krauthgamer and resolves their open conjecture up to a logarithmic factor, matching the $\Omega (n^2)$ lower bound from directed cuts. Motivated by capacity budgets in submodular applications and the Restricted Isometry Property (RIP) in compressed sensing, we further study submodular sparsification under a cardinality constraint $|S|\le k$, and obtain a polynomial-time algorithm that constructs a sparsifier of size $O(nk\log n/{\epsilon }^2)$, nearly matching the $\Omega (nk)$ lower bound. This shows that a cardinality constraint unconditionally reduces the size of general submodular sparsifiers by a factor of roughly $k/n$; we complement this with $\Omega (n)$ lower bounds showing that even regular symmetric or almost-regular monotone submodular functions cannot be sparsified to $o(n)$ size for $k=2$ and $k=1$, respectively.