Given a directed graph, \(G=(V,E)\), a path query, \(\operatorname{path}(u,v)\), returns whether there is a directed path from \(u\) to \(v\) in \(G\), for \(u,v \in V\). Given only \(V\), exactly learning all the edges in \(G\) using path queries is often impossible, since path queries cannot detect transitive edges. In this paper, we study the query complexity of exact learning for cases when learning \(G\) is possible using path queries. In particular, we provide efficient learning algorithms, as well as lower bounds, for multitrees and almost-trees, including butterfly networks.
(Joint work with Michael Goodrich.)