Learning a Hidden Graph Using O(log N) Queries per Edge

Abstract

We consider the problem of learning a general graph using edge-detecting queries. In this model, the learner may query whether a set of vertices induces an edge of the hidden graph. This model has been studied for particular classes of graphs by Kucherov and Grebinski [1] and Alon et al. [2], motivated by problems arising in genome sequencing. We give an adaptive deterministic algorithm that learns a general graph with n vertices and m edges using O ( m log n ) queries, which is tight up to a constant factor for classes of non-dense graphs. Allowing randomness, we give a 5-round Las Vegas algorithm using $O(m {\rm log}n+\sqrt{m}{\rm log}^{2}n)$ queries in expectation. We give a lower bound of Ω((2 m / r )^ r /2) for learning the class of non-uniform hypergraphs of dimension r with m edges. For the class of r -uniform hypergraphs with bounded degree d , where d ≤ n ^1/( r− − 1)/(2 r ^1 + 2/( r− − 1)), we give a non-adaptive Monte Carlo algorithm using O ( dn log n ) queries, which succeeds with probability at least 1– n ^ − − c, where c is any constant.