On Learning a Hidden Directed Graph with Path Queries

02/26/2020
by   Mano Vikash Janardhanan, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset