Reconstructing a Bounded-Degree Directed Tree Using Path Queries

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.