On Learning Graphs with Edge-Detecting Queries

We consider the problem of learning a general graph G=(V,E) using edge-detecting queries, where the number of vertices |V|=n is given to the learner. The information theoretic lower bound gives mlog n for the number of queries, where m=|E| is the number of edges. In case the number of edges m is also given to the learner, Angluin-Chen's Las Vegas algorithm citeAC08 runs in 4 rounds and detects the edges in O(mlog n) queries. In the other harder case where the number of edges m is unknown, their algorithm runs in 5 rounds and asks O(mlog n+√mlog2 n) queries. There have been two open problems: (i) can the number of queries be reduced to O(mlog n) in the second case, and, (ii) can the number of rounds be reduced without substantially increasing the number of queries (in both cases). For the first open problem (when m is unknown) we give two algorithms. The first is an O(1)-round Las Vegas algorithm that asks mlog n+√m(log[k]n)log n queries for any constant k where log[k]n=log stackrelkcdots log n. The second is an O(log^*n)-round Las Vegas algorithm that asks O(mlog n) queries. This solves the first open problem for any practical n, for example, n<265536. We also show that no deterministic algorithm can solve this problem in a constant number of rounds. To solve the second problem we study the case when m is known. We first show that any non-adaptive Monte Carlo algorithm (one-round) must ask at least Omega(m2log n) queries, and any two-round Las Vegas algorithm must ask at least m4/3-o(1)log n queries on average. We then give two two-round Monte Carlo algorithms, the first asks O(m4/3log n) queries for any n and m, and the second asks O(mlog n) queries when n>2m. Finally, we give a 3-round Monte Carlo algorithm that asks O(mlog n) queries for any n and m.