2022/01/13 by Bhattacharya, Anup, Bishnu, Arijit, Ghosh, Arijit +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2201.04975
In this work, we consider d-\sc Hyperedge Estimation and d-\sc Hyperedge Sample problem in a hypergraph H(U(H),F(H)) in the query complexity framework, where U(H) denotes the set of vertices and F(H) denotes the set of hyperedges. The oracle access to the hypergraph is called \sc Colorful Independence Oracle (\sc CID), which takes d (non-empty) pairwise disjoint subsets of vertices A1,…,Ad ⊆ U(H) as input, and answers whether there exists a hyperedge in H having (exactly) one vertex in each Ai, i ∈ \1,2,…,d\. The problem of d-\sc Hyperedge Estimation and d-\sc Hyperedge Sample with \sc CID oracle access is important in its own right as a combinatorial problem. Also, Dell \itet al.~[SODA '20] established that \em decision vs \em counting complexities of a number of combinatorial optimization problems can be abstracted out as d-\sc Hyperedge Estimation problems with a \sc CID oracle access. The main technical contribution of the paper is an algorithm that estimates m= | F(H)| with \widehatm such that \frac1Cdlogd-1 n ≤ \frac\widehatmm ≤ Cd log d-1 n . by using at most Cdlog d+2 n many \sc CID queries, where n denotes the number of vertices in the hypergraph H and Cd is a constant that depends only on d. Our result coupled with the framework of Dell \itet al.~[SODA '21] implies improved bounds for a number of fundamental problems.