Learning a hidden subgraph

Noga Alon, Vera Asodi

Research output: Chapter in Book/Report/Conference proceedingChapter

7 Scopus citations

Abstract

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)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJosep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella
PublisherSpringer Verlag
Pages110-121
Number of pages12
ISBN (Print)3540228497
DOIs
StatePublished - 2004
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3142
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this

    Alon, N., & Asodi, V. (2004). Learning a hidden subgraph. In J. Díaz, J. Karhumäki, A. Lepistö, & D. Sannella (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 110-121). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3142). Springer Verlag. https://doi.org/10.1007/978-3-540-27836-8_12