# Exact Learning of Multitrees and Almost-Trees Using Path Queries

arXiv: https://arxiv.org/abs/2208.04216 · HTML: https://mlsanity.com/paper/2208.04216/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Aug 2022.

## Built on by (most cited first, 1 of 1)

- [Exact Learning of Weighted Graphs Using Composite Queries](https://mlsanity.com/paper/2511.14882/) (2025)

## Abstract (arXiv)

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.