# Reconstructing a Bounded-Degree Directed Tree Using Path Queries

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Jun 2016.

## 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)

We present a randomized algorithm for reconstructing directed rooted trees of n nodes and node degree at most d, by asking at most O(dnlog2 n) path queries. Each path query takes as input an origin node and a target node, and answers whether there is a directed path from the origin to the target. Regarding lower bounds, we show that any randomized algorithm requires at least Omega(nlog n) queries, while any deterministic algorithm requires at least Omega(dn) queries. Additionally, we present a O(dnlog3 n) randomized algorithm for noisy queries, and a O(dnlog2 n) randomized algorithm for additive queries on weighted trees.