Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers

A (1) -sparsifier of a hypergraph G (V, E) is a (weighted) subgraph that preserves the value of every cut to within a (1) -factor. It is known that every hypergraph with n vertices admits a (1) -sparsifier with O (n/²) hyperedges. In this work, we explore the task of building such a sparsifier by using only linear measurements (a linear sketch) over the hyperedges of G, and provide nearly-matching upper and lower bounds for this task. Specifically, we show that there is a randomized linear sketch of size O (n r (m) / ²) bits which with high probability contains sufficient information to recover a (1) cut-sparsifier with O (n/²) hyperedges for any hypergraph with at most m edges each of which has arity bounded by r. This immediately gives a dynamic streaming algorithm for hypergraph cut sparsification with an identical space complexity, improving on the previous best known bound of O (n r² ⁴ (m) / ²) bits of space (Guha, McGregor, and Tench, PODS 2015). We complement our algorithmic result above with a nearly-matching lower bound. We show that for every (0, 1), one needs (nr (m/n) / (n) ) bits to construct a (1) -sparsifier via linear sketching, thus showing that our linear sketch achieves an optimal dependence on both r and (m).