Learning a hidden subgraph

Noga Alon, Vera Asodi

Research output: Contribution to journalArticlepeer-review

68 Scopus citations


We consider the problem of learning a labeled graph from a given family of graphs on n vertices in a model where the only allowed operation is to query whether a set of vertices induces an edge. Questions of this type are motivated by problems in molecular biology. In the deterministic nonadaptive setting, we prove nearly matching upper and lower bounds for the minimum possible number of queries required when the family is the family of all stars of a given size or all cliques of a given size. We further describe some bounds that apply to general graphs.

Original languageEnglish (US)
Pages (from-to)697-712
Number of pages16
JournalSIAM Journal on Discrete Mathematics
Issue number4
StatePublished - 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics


  • Complete graphs
  • Hidden subgraphs
  • Stars


Dive into the research topics of 'Learning a hidden subgraph'. Together they form a unique fingerprint.

Cite this