Sublinear Time Hypergraph Sparsification via Cut and Edge Sampling Queries

The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Bencz'ur and Karger (1996) showed that given any n-vertex undirected weighted graph G and a parameter varepsilon ∈ (0,1), there is a near-linear time algorithm that outputs a weighted subgraph G' of G of size tildeO(n/varepsilon2) such that the weight of every cut in G is preserved to within a (1 ± varepsilon)-factor in G'. The graph G' is referred to as a em (1 ± varepsilon)-approximate cut sparsifier of G. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require Omega(n + m) time where n denotes the number of vertices and m denotes the number of hyperedges in the hypergraph. Since m can be exponentially large in n, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in n, em independent of the number of edges. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph.