Bhattacharya, Anup ;
Bishnu, Arijit ;
Ghosh, Arijit ;
Mishra, Gopinath
Faster Counting and Sampling Algorithms Using Colorful Decision Oracle
Abstract
In this work, we consider dHyperedge Estimation and dHyperedge 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 Colorful Independence Oracle (CID), which takes d (nonempty) pairwise disjoint subsets of vertices A₁,…, A_d ⊆ U(ℋ) as input, and answers whether there exists a hyperedge in H having (exactly) one vertex in each A_i, i ∈ {1,2,…,d}. The problem of dHyperedge Estimation and dHyperedge Sample with CID oracle access is important in its own right as a combinatorial problem. Also, Dell et al. [SODA '20] established that decision vs counting complexities of a number of combinatorial optimization problems can be abstracted out as dHyperedge Estimation problems with a CID oracle access.
The main technical contribution of the paper is an algorithm that estimates m = F(H) with m̂ such that
1/(C_{d)log^{d1} n) ≤ m̂/m ≤ C_{d} log ^{d1} n.
by using at most C_{d}log ^{d+2} n many CID queries, where n denotes the number of vertices in the hypergraph H and C_d is a constant that depends only on d}. Our result coupled with the framework of Dell et al. [SODA '21] implies improved bounds for the following fundamental problems:
Edge Estimation using the Bipartite Independent Set (BIS). We improve the bound obtained by Beame et al. [ITCS '18, TALG '20].
Triangle Estimation using the Tripartite Independent Set (TIS). The previous best bound for the case of graphs with low codegree (Codegree for an edge in the graph is the number of triangles incident to that edge in the graph) was due to Bhattacharya et al. [ISAAC '19, TOCS '21], and Dell {et al.}’s result gives the best bound for the case of general graphs [SODA '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 '21].
BibTeX  Entry
@InProceedings{bhattacharya_et_al:LIPIcs.STACS.2022.10,
author = {Bhattacharya, Anup and Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath},
title = {{Faster Counting and Sampling Algorithms Using Colorful Decision Oracle}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {10:110:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15820},
URN = {urn:nbn:de:0030drops158205},
doi = {10.4230/LIPIcs.STACS.2022.10},
annote = {Keywords: Query Complexity, Subset Query, Hyperedge Estimation, and Colorful Independent Set oracle}
}
09.03.2022
Keywords: 

Query Complexity, Subset Query, Hyperedge Estimation, and Colorful Independent Set oracle 
Seminar: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Issue date: 

2022 
Date of publication: 

09.03.2022 