Exact Learning of Multitrees and Almost-Trees Using Path Queries

2022/08/08 by Afshar, Ramtin, Goodrich, Michael T. · 1 citation
#Data Structures and Algorithms (cs.DS) #E.2 #F.2.0 #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2208.04216

Abstract

Given a directed graph, G=(V,E), a path query, path(u,v), returns whether there is a directed path from u to v in G, for u,v vertices 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.

Cited by

• Exact Learning of Weighted Graphs Using Composite Queries

Related

• On Learning a Hidden Directed Graph with Path Queries
• Near-Linear Query Complexity for Graph Inference
• Distance-based Learning of Hypertrees
• Reconstructing a Bounded-Degree Directed Tree Using Path Queries
• Quasi-linear distance query reconstruction for graphs of bounded treelength