Learning a hidden graph using O(logn) queries per edge

摘要

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 Grebinski and Kucherov [V. Grebinski, G. Kucherov, Optimal query bounds for reconstructing a Hamiltonian cycle in complete graphs, in: Fifth Israel Symposium on the Theory of Computing Systems, 1997, pp. 166–173] and Alon et al. [N. Alon, R. Beigel, S. Kasif, S. Rudich, B. Sudakov, Learning a hidden matching, in: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 197–206], 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(mlogn) 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(mlogn+mlog2n) queries in expectation. We give a lower bound of Ω((2m/r)r/2) for learning the class of non-uniform hypergraphs of dimension r with m edges.