  We investigate the number of maximal independent set queries required to
reconstruct the edges of a hidden graph. We show that randomised adaptive
algorithms need at least $\Omega(\Delta^2 \log(n / \Delta) / \log \Delta)$
queries to reconstruct $n$-vertex graphs of maximum degree $\Delta$ with
success probability at least $1/2$, and we further improve this lower bound to
$\Omega(\Delta^2 \log(n / \Delta))$ for randomised non-adaptive algorithms. We
also prove that deterministic non-adaptive algorithms require at least
$\Omega(\Delta^3 \log n / \log \Delta)$ queries.
  This improves bounds of Konrad, O'Sullivan, and Traistaru, and answers one of
their questions. The proof of the lower bound for deterministic non-adaptive
algorithms relies on a connection to cover-free families, for which we also
improve known bounds.
