Edge Estimation with Independent Set Oracles

Paul Beame, Sariel Har-Peled, S. N. Ramamoorthy, Cyrus Rashtchian, Makrand Sinha

Research output: Contribution to journalArticlepeer-review

Abstract

We study the task of estimating the number of edges in a graph, where the access to the graph is provided via an independent set oracle. Independent set queries draw motivation from group testing and have applications to the complexity of decision versus counting problems. We give two algorithms to estimate the number of edges in an n-vertex graph, using (i) polylog(n) bipartite independent set queries or (ii) n2/3 polylog(n) independent set queries.

Original languageEnglish (US)
Article number3404867
JournalACM Transactions on Algorithms
Volume16
Issue number4
DOIs
StatePublished - Sep 2020

Keywords

  • Independent set queries
  • graph parameter estimation

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint

Dive into the research topics of 'Edge Estimation with Independent Set Oracles'. Together they form a unique fingerprint.

Cite this