On Learning a Hidden Directed Graph with Path Queries
  In this paper, we consider the problem of reconstructing a directed graph
using path queries. In this query model of learning, a graph is hidden from the
learner, and the learner can access information about it with path queries. For
a source and destination node, a path query returns whether there is a directed
path from the source to the destination node in the hidden graph. In this paper
we first give bounds for learning graphs on $n$ vertices and $k$ strongly
connected components. We then study the case of bounded degree directed trees
and give new algorithms for learning "almost-trees" -- directed trees to which
extra edges have been added. We also give some lower bound constructions
justifying our approach.
