Hyperedge Estimation using Polylogarithmic Subset Queries

Abstract

In this work, we estimate the number of hyperedges in a hypergraph $\mathcal{H}(U(\mathcal{H}),\mathcal{F}(\mathcal{H}))$, where $U(\mathcal{H})$ denotes the set of vertices and $\mathcal{F}(\mathcal{H}))$ denotes the set of hyperedges. We assume a query oracle access to the hypergraph $\mathcal{H}$. Estimating the number of edges, triangles or small subgraphs in a graph is a well studied problem. Beame \etal~and Bhattacharya \etal~gave algorithms to estimate the number of edges and triangles in a graph using queries to the {\sc Bipartite Independent Set} ({\sc BIS}) and the {\sc Tripartite Independent Set} ({\sc TIS}) oracles, respectively. We generalize the earlier works by estimating the number of hyperedges using a query oracle, known as the {\bf Generalized $d$-partite independent set oracle ({\sc GPIS})}, that takes $d$ (non-empty) pairwise disjoint subsets of vertices $A_1,\dots ,A_d\subseteq U(\mathcal{H})$ as input, and answers whether there exists a hyperedge in $\mathcal{H}$ having (exactly) one vertex in each $A_i,i\in \{1,2,\dots ,d\}$. We give a randomized algorithm for the hyperedge estimation problem using the {\sc GPIS} query oracle to output $\hat{m}$ for $m(\mathcal{H})$ satisfying $(1-\epsilon )\cdot m(\mathcal{H})\le \hat{m}\le (1+\epsilon )\cdot m(\mathcal{H})$. The number of queries made by our algorithm, assuming $d$ to be a constant, is polylogarithmic in the number of vertices of the hypergraph.

34 pages