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 runs in $4$ rounds and detects the edges in $O(mlog n)$ queries. In the harder case where the number of edges $m$ is unknown, their algorithm runs in $5$ rounds and asks $O(mlog n+sqrt{m}log^2 n)$ queries. They presented 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+sqrt{m}(log^{[k]}n)log n$ queries for any constant $k$ where $log^{[k]}n=log stackrel{k}{cdots} 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, $n2^m$. Finally, we give a $3$-round Monte Carlo algorithm that asks $O(mlog n)$ queries for any $n$ and $m$.