DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.41

From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries

Authors: Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, and Gopinath Mishra

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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 Õ(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.

Cite as

Debarshi Chanda, Buddha Dev Das, Arijit Ghosh, and Gopinath Mishra. From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 41:1-41:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chanda_et_al:LIPIcs.APPROX/RANDOM.2026.41,
  author =	{Chanda, Debarshi and Das, Buddha Dev and Ghosh, Arijit and Mishra, Gopinath},
  title =	{{From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{41:1--41:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.41},
  URN =		{urn:nbn:de:0030-drops-277584},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.41},
  annote =	{Keywords: Property Testing, Edge Estimation}
}

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.55

Arboricity Matters in Triangle Counting with Random Edges

Authors: Arijit Bishnu, Debarshi Chanda, and Gopinath Mishra

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

Given a simple, unweighted, undirected graph G = (V,E) with |V| = n and |E| = m, and parameters 0 < ε, δ < 1, along with Degree, Neighbour, Pair and RandomEdge query access to G, we provide a query-based randomized algorithm to generate an estimate T̂ of the number of triangles T in G, such that T̂ ∈ [(1-ε)T , (1+ε)T] with probability at least 1-δ. The query complexity of our algorithm is Õ(m α log(1/δ)/{ε³T}), where α is the arboricity of G. Our work can be seen as a natural progression to the line of recent works [Eden et al., SIAM J Comp., 2017; Assadi et al., ITCS 2019; Eden et al., SODA 2020] that considered subgraph or triangle counting with or without the use of RandomEdge query. Of these works, Eden et al. [SODA 2020] considers the role of arboricity. Our work is the first to consider how RandomEdge query can leverage the structural property of arboricity. Furthermore, continuing in the line of work of Assadi et al. [APPROX/RANDOM 2022], we also provide a lower bound of Ω̃(m α log(1/δ)/{ε²T}) that matches the upper bound exactly on arboricity, δ, and almost on ε.

Cite as

Arijit Bishnu, Debarshi Chanda, and Gopinath Mishra. Arboricity Matters in Triangle Counting with Random Edges. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 55:1-55:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bishnu_et_al:LIPIcs.APPROX/RANDOM.2026.55,
  author =	{Bishnu, Arijit and Chanda, Debarshi and Mishra, Gopinath},
  title =	{{Arboricity Matters in Triangle Counting with Random Edges}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{55:1--55:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.55},
  URN =		{urn:nbn:de:0030-drops-277722},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.55},
  annote =	{Keywords: Triangle counting, Sublinear algorithms, Subgraph counting}
}

Search Results

Documents authored by Chanda, Debarshi

From Decision to Random Certificates: Exponential Separation for Edge Estimation with Independent Set Queries

Abstract

Cite as

Arboricity Matters in Triangle Counting with Random Edges

Abstract

Cite as

Thanks for your feedback!

Could not send message