2026-09-10T09:45:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27758 2026-09-09T12:19:37Z ddc:004 open_access

From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries Chanda, Debarshi Das, Buddha Dev Ghosh, Arijit Mishra, Gopinath Property Testing Edge Estimation We study the problem of estimating the number of edges in an undirected, unweighted graph using sublinear query access. We consider a query model that preserves the structure of Independent Set (IS) queries, but augments their output with a random certificate: given a vertex subset, the oracle returns a uniformly random edge from the induced subgraph if one exists, and returns null otherwise. Using this access, we give a randomized algorithm that outputs a (1 ± ε)-approximation to the number of edges with constant success probability using Õ(log² m) queries. This implies an exponential separation from both standard IS queries and global random edge-sampling models: estimating the number of edges using standard IS queries require Θ̃(min {√m, n/√m}) queries, while direct random edge-sample access requires Θ̃(√m) samples. Beyond separation in query complexity, our algorithm is output-sensitive: its query complexity is polylogarithmic in the number of edges in the graph. This aligns with the classical objective in group testing, where one seeks algorithms that are both worst-case optimal and instance-adaptive. Conceptually, our model connects group testing, the decision-versus-counting dichotomy, graph property testing, and the "power of a random certificate", and can be viewed as a structured form of conditional sampling of edges in graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Debarshi Chanda and Buddha Dev Das and Arijit Ghosh and Gopinath Mishra 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.41 urn:nbn:de:0030-drops-277584 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.41 eng https://creativecommons.org/licenses/by/4.0/legalcode