DOI: 10.1145/3657605 ISSN: 19423454
Faster Counting and Sampling Algorithms using Colorful Decision Oracle
Anup Bhattacharya, Arijit Bishnu, Arijit Ghosh, Gopinath Mishra Computational Theory and Mathematics
 Theoretical Computer Science
In this work, we consider d 
Hyperedge Estimation
and
d

Hyperedge Sample
problems, that deal with estimation and uniform sampling of hyperedges in a hypergraph
Colorful Independence Oracle
(
CID
), which takes
d
(nonempty) pairwise disjoint subsets of vertices
Hyperedge Estimation
and
d

Hyperedge Sample
problems with
CID
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

Hyperedge Estimation
problem with a
CID
oracle access.
The main technical contribution of this paper is an algorithm that estimates
CID
queries, where
n
denotes the number of vertices in the hypergraph
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
codegree
(codegree 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].