Learning a Hidden Subgraph | Zendy

Noga Alon | Zendy; Vera Asodi | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Learning a Hidden Subgraph

Author(s) -

Noga Alon,

Vera Asodi

Publication year - 2005

Publication title -

siam journal on discrete mathematics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.843

H-Index - 66

eISSN - 1095-7146

pISSN - 0895-4801

DOI - 10.1137/s0895480103431071

Subject(s) - combinatorics , mathematics , induced subgraph isomorphism problem , upper and lower bounds , matching (statistics) , discrete mathematics , induced subgraph , independent set , graph , set (abstract data type) , line graph , computer science , vertex (graph theory) , mathematical analysis , statistics , voltage graph , programming language

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research