Faster Counting and Sampling Algorithms using Colorful Decision Oracle

In this work, we consider d -

and d - problems, that deal with estimation and uniform sampling of hyperedges in a hypergraph \(\mathcal {H}(U(\mathcal {H}),\mathcal {F}(\mathcal {H})) \) in the query complexity framework, where \(U(\mathcal {H}) \) denotes the set of vertices and \(\mathcal {F}(\mathcal {H}) \) denotes the set of hyperedges. The oracle access to the hypergraph is called ( ), which takes d (non-empty) pairwise disjoint subsets of vertices \(A_1,\ldots,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 for all i ∈ {1, 2, …, d }. Apart from the fact that d - and d - problems with oracle access seem to be nice combinatorial problems, Dell et al.  [SODA’20 & SICOMP’22] established that decision vs counting complexities of a number of combinatorial optimization problems can be abstracted out as d - problem with a oracle access.

The main technical contribution of this paper is an algorithm that estimates \(m= |\mathcal {F}(\mathcal {H})| \) with \(\hat{m} \) such that \[ \frac{1}{C_{d}\log ^{d-1} n} \;\le \; \frac{\hat{m}}{m} \;\le \; C_{d} \log ^{d-1} n. \] by using at most C _d log  ^{d + 2} n

queries, where n denotes the number of vertices in the hypergraph \(\mathcal {H} \) and C _d is a constant that depends only on d . Our result, when combin coupled with the framework proposed byof Dell et al.  [SODA’20 & SICOMP’22], leads to implies improved bounds for (1 ± ε)-approximation (where ε ∈ (0, 1)) for the following fundamental problems:

Edge Estimation

using the

Bipartite Independent Set

(

BIS

) query. We improve the bound obtained by Beame et al.  [ITCS’18 & TALG’20].

Triangle Estimation

using the

Tripartite Independent Set

(

TIS

) query. Currently, Dell et al. ’s result gives the best bound for the case of triangle estimation in general graphs [SODA’20 & SICOMP’22]. The previous best bound for the case of graphs with low co-degree (co-degree of a graph is the maximum number of triangles incident over any edge of the graph) was due to Bhattacharya et al.  [ISAAC’19 & TOCS’21]. We improve both of these bounds.

Hyperedge Estimation & Sampling

using

Colorful Independence Oracle

(

CID

). We give an improvement over the bounds obtained by Dell et al.  [SODA ’20 & SICOMP ’22].