On Learning a Hidden Directed Graph with Path Queries
This addresses a fundamental problem in graph learning and query models, with potential applications in network analysis and data structures, but it appears incremental as it builds on existing query-based approaches.
The paper tackles the problem of reconstructing a hidden directed graph using path queries, which return whether a directed path exists between two nodes, and provides bounds for graphs with n vertices and k strongly connected components, along with new algorithms for learning bounded-degree directed trees and 'almost-trees' with extra edges.
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.