Reconstructing a Bounded-Degree Directed Tree
Using Path Queries

arXiv:1606.05183v3 [cs.DS] 16 Nov 2017

Zhaosen Wang
CS, Purdue
West Lafayette, IN 47907, USA
wang2055@purdue.edu

Jean Honorio
CS, Purdue
West Lafayette, IN 47907, USA
jhonorio@purdue.edu

Abstract
We present a randomized algorithm for reconstructing directed rooted trees of n nodes and
node degree at most d, by asking at most O(dn log2 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 Ω(n log n) queries, while any deterministic algorithm requires at least Ω(dn)
queries. Additionally, we present a O(dn log3 n) randomized algorithm for noisy queries, and
a O(dn log2 n) randomized algorithm for additive queries on weighted trees.

1

Introduction

Scientists in diverse areas, such as statistics, epidemiology and economics, aim to unveil relationships within variables from collected data. This process can be seen as the task of reconstructing
a graph (i.e., finding the hidden edges of a graph) by asking queries to an oracle. In this graph,
each vertex is a variable, and each edge denotes the relationship between two variables. For
instance, in cancer research, biologists try to discover the causal relationships between genes. By
providing a specific treatment to a particular gene (origin), biologists can observe whether there is
an effect in another gene (target). This effect can be either direct (if the two genes are connected
with a directed edge) or indirect (if there is a directed path from the origin to the target gene.)
In the above example, we can think of nature as the oracle that is answering whether there is a
directed path from an origin to a target node. Arguably, the cost of asking queries is very high
in several application domains. Thus, we are interested on the reconstruction of graphs that do
not require the trivial n2 queries for n nodes (i.e., one query for every possible pair of nodes.)
Prior work on reconstructing graphs has exclusively focused on undirected graphs. In [11], a
O(dn log n) algorithm was provided for recovering undirected trees of n nodes and maximum node
degree d, by using queries that return the path length between two given nodes. Authors of [5]
provide a O(dn) algorithm for reconstructing undirected trees of n nodes and maximum node
degree d, and for a query that returns the distance from a given node to every other node. The
results in [2, 3, 4] pertain to queries that answer whether there exists at least one edge between
a given set of nodes. While [2, 3] focused on matchings and stars, the work of [4] provides a
O(m log n) algorithm for undirected graphs of n nodes and m edges. The results in [10, 14]
pertain to queries that return the number of edges between a given set of nodes. A O(dn)
algorithm was provided in [10] for undirected graphs of n nodes and maximum node degree d,
while a O(m log n) algorithm was given in [14] for undirected graphs of n nodes and m edges.
Other works have focused on the recovery of weighted undirected graphs. The work of [9] provides
a O(dn log n) algorithm for recovering weighted undirected trees of n nodes and maximum node
degree d, by using queries that return the sum of edge weights on the path between two given
nodes. The work of [6,13] pertains to the reconstruction of weighted undirected graphs of n nodes

1

and m edges. A O(m log n) algorithm was provided for a query that gives the sum of edge weights
between a given set of nodes.
The closest work to ours is [12], which provides a O(dn log2 n) randomized algorithm for
undirected trees of n nodes and maximum node degree d, and for separator queries. A separator
query takes three nodes i, k, j as input, and answers whether k is on the undirected path between
i and j. In contrast, our work pertains to directed rooted trees. Furthermore, we use a different
type of query which we call path query. A path query takes an ordered pair of nodes i, j as input,
and answers whether there exists a directed path from i to j.
We provide a randomized algorithm for reconstructing directed rooted trees of n nodes and
node degree at most d, in O(dn log2 n) time. To the best of our knowledge, there is no simple
reduction to transform our problem to the problem of [12] or any of the above mentioned literature.
Our algorithm relies on the divide and conquer approach, the use of even separators [7] and
sorting. Regarding lower bounds, we show that any randomized algorithm requires at least
Ω(n log n) queries, while any deterministic algorithm requires at least Ω(dn) queries. We also
present a O(dn log3 n) randomized algorithm for a noisy regime, in which the bit that represents
the oracle’s answer gets flipped with some probability, by an adversary, before it is revealed to
the algorithm. Furthermore, we present a O(dn log2 n) randomized algorithm for reconstructing
weighted trees by using additive queries that return the sum of the edge weights on the directed
path between two given nodes. We finish the paper by showing some negative results that provide
some motivation for our assumptions. We show that any deterministic or randomized algorithm
requires at least Ω(n2 ) queries in order to recover more general directed acyclic graphs. We also
show that any deterministic algorithm requires at least Ω(n2 ) queries for recovering a family of
sparse disconnected graphs, as well as a family of sparse connected graphs.

2

Preliminaries

In this section, we provide several formal definitions which will be useful later for the detailed
description of our algorithm. For clarity, we also provide some preliminary introduction to the
main aspects of our algorithm.
Let G = (V, E) be a directed acyclic graph with vertex set V and edge set E. For clarity,
when G is a directed rooted tree, we will use T instead of G. In this paper, we assume that T
has n nodes, i.e., |V | = n. Furthermore, we also assume that the node degree is at most d. (In a
directed acyclic graph, the node degree is the sum of the indegree and the outdegree of the node.)
Recall that a path in G from node i to node j (both in V ) is a sequence of nodes i, x1 , x2 , . . . xk , j
such that {(i, x1 ), (x1 , x2 ), . . . (xk−1 , xk ), (xk , j)} is a subset of the edge set E.
Our algorithm reconstructs a directed rooted tree, by using path queries. Next, we formally
define path queries.
Definition 1. Let G = (V, E) be a directed acyclic graph. A path query is a function QG :
V × V → {0, 1} such that QG (i, j) = 1 if there exists a path in G from i to j, and QG (i, j) = 0
otherwise.
Note that the above query only reveals a single bit of information, and it does not provide
any information regarding the length of the path, thus making graph reconstruction a nontrivial
task.
In this paper, we assume that the node set V is known, while edge set E is unknown. Our
main problem is indeed to reconstruct E by using path queries. We will use Q(i, j) to denote
QT (i, j) since for our problem, the directed rooted tree T is fixed (but unknown).
2

1
6

7

2

3

4

5

8

9

11

10

(a)

1
6

7

2

3

4

5

8

9

11

10

(b)

Figure 1: (a) A directed rooted tree with multidirectional path of nodes 1, 2, 3, 4, 5. Nodes and
edges in the multidirectional path are shown in red. (b) Skeleton graph of the directed rooted
tree on the left, with path of nodes 1, 2, 3, 4, 5. Nodes and edges in the path are shown in red.
1
6

7

2

3

8

9

4

5
11

10
Figure 2: A directed rooted tree with multidirectional path of nodes 1, 2, 3, 4, 5. Nodes and edges
in the multidirectional path are shown in red. The edge (2, 3) in the multidirectional path is an
even separator. Our algorithm will recursively recover each of the two generated subtrees (shown
as blue boxes.)
A key step in our algorithm is the recovery of what we call multidirectional paths. A multidirectional path consists of the directed edges associated to an undirected path in the skeleton
graph (i.e., the graph obtained by replacing each directed edge with an undirected edge in the
original graph.) Figure 1 provides a visual illustration for intuitive understanding. Next, we
formally define multidirectional paths.
Definition 2. Let G = (V, E) be a directed acyclic graph. A multidirectional path of G between i
and j is a sequence of nodes i, x1 , x2 , . . . , xk−1 , xk , j such that each node in V appears at most once
in the sequence, and that there is an edge on either direction between each pair of adjacent nodes
in the sequence. That is, either (i, x1 ) ∈ E or (x1 , i) ∈ E, either (x1 , x2 ) ∈ E or (x2 , x1 ) ∈ E,
. . . either (xk−1 , xk ) ∈ E or (xk , xk−1 ) ∈ E, and either (xk , j) ∈ E or (j, xk ) ∈ E.
Next, we show that for directed rooted trees, a multidirectional path between any two arbitrary
nodes always exists and is unique. More importantly, we show that a multidirectional path is
either a directed path, or two directed paths that share the same origin (i.e., the lowest common
ancestor.) Later, we leverage this property for recovering multidirectional paths.
Lemma 1. Let T = (V, E) be a directed rooted tree. Given any two arbitrary nodes i and
j, a multidirectional path of T between i and j always exists and is unique. Furthermore, a
multidirectional path of T between i and j, is either a path from i to j, or a path from j to i, or
two paths (one from k to i, and one from k to j, for some k ∈ V − {i, j}.) In this case, node k
is the lowest common ancestor of i and j.
(See Appendix B for detailed proofs.)
Our algorithm relies on the divide and conquer approach. In order to apply the above approach
in our problem, it is important to introduce the concepts of even separators and bags. Next, we
introduce even separators.
3

1
6

7

2

3

8

9

4

5

1

11

6

7

2

3

8

9

10

4

11

10
(a)

1
6

7

2

3

8

9

5

4

(b)

5

1

11

6

10

7

2

3

8

9

4

5
11

10
(c)

(d)

Figure 3: Four different directed rooted trees, and their bags with respect to the multidirectional
path of nodes 1, 2, 3, 4, 5. Nodes and edges in the multidirectional path are shown in red. The
lowest common ancestor of nodes 1 and 5 in the multidirectional path is shown in darker red. A
tree root is shown as a thick circle. Bags are shown as blue boxes. Note that a multidirectional
path can be a path (a,c) or two paths (b,d). The root can be in the multidirectional path (a,b).
Otherwise, the root can be an ancestor of a node in the multidirectional path (c,d).
Definition 3. Let T = (V, E) be a directed rooted tree of bounded degree d and let n = |V |. An
even separator of T is an edge e ∈ E that when removed from T , divides T into two subtrees T1
and T2 , where each of the subtrees have a number of nodes between n/d and (d − 1)n/d.
The existence of even separators is pivotal for using divide and conquer in our problem.
Corollary 2.3 in [7] shows that if a graph is a bounded-degree directed tree, then an even separator
exists. For our graph reconstruction problem, once the even separator is identified, we cut the tree
through the even separator. This operation splits the tree into two subtrees. We then recursively
call the algorithm for both subtrees. We illustrate this in Figure 2.
While even separators exist [7], it remains to know whether they can be efficiently found. We
show later that (on average) there is an even separator in the multidirectional path between two
nodes chosen independently and uniformly at random (See Theorem 1.)
In what follows, we formally define bags, which are also important for the divide and conquer
approach taken here.
Definition 4. Let T = (V, E) be a directed rooted tree, and S be the set of edges in a multidirectional path of T . Define TS = (V, E − S) as the subgraph of T after we remove all edges in S. A
bag with respect to a node i in a multidirectional path with edges S, is a subset of nodes in V that
contains i and all the nodes that are reachable from i in the (undirected) skeleton graph of TS .
Intuitively speaking, we can think of edges in a tree as “ropes”. If we “nail” all nodes of a
multidirectional path into the “wall”, then all other nodes will “hang” from one of the nodes in
the path. Nodes that hang from the same particular node belong to the same bag. We include a
visual example in Figure 3.
In our algorithm, we recover exactly all the directed edges in a multidirectional path. Bags are
used to count the number of nodes associated to each node in the multidirectional path (without
the need to recover all the directed edges.) For each edge in the multidirectional path, one can

4

Alg. 1: Reconstruct tree
O(dn log2 n)
Alg. 2: Reconstruct multidirectional path
O(n log n)

Alg. 5: Find bag
O(log n)

Alg. 6: Split tree
O(n)

if multidirectional path consists of two paths
Alg. 3: Find lowest common ancestor
O(n log n)

Alg. 4: Find path from root
O(n log n)

Figure 4: Main algorithm (in red), subroutines, and their time complexity.
then count the number of nodes on the two subtrees that would be generated if we were to cut
the tree through the given edge. This process is used for identifying even separators.
Finally, our algorithm also performs sorting of nodes with a properly defined order relation,
which is used for instance in the recovery of the directed edges in multidirectional paths.
Definition 5. Define the order relation of two nodes i and j as follows. If Q(i, j) = 1 we say
that i is “less than” j, and “greater than” otherwise.

3

Algorithm

In this section, we present our randomized algorithm and analyze its time complexity. Our
algorithm is similar in spirit to [12] which applies to undirected trees and separator queries. In
this paper, we focus on directed rooted trees and path queries. We remind the reader that path
queries only reveal a single bit of information, and they do not provide any information regarding
the length of the path. (We discuss noisy and additive extensions in Section 4.)
In what follows, we explain our divide and conquer approach in our main Algorithm 1. A
high-level overview is shown in Figure 4. (See Appendix A for detailed algorithms.) First, we
randomly pick two nodes and recover the sequence of nodes in the multidirectional path between
those two randomly chosen nodes (Algorithm 2.) Then, we divide the rest of the nodes (not in
the multidirectional path) into bags defined by the multidirectional path (Algorithm 5.) Later,
we count the number of nodes on each bag, and determine if there exists an even separator in the
multidirectional path. We repeat the whole procedure (i.e., from choosing a new pair of random
nodes) until we find an even separator. Finally, we cut the tree through the even separator,
thus effectively splitting the tree into two subtrees (Algorithm 6.) We then recursively call our
Algorithm 1 for both subtrees (until the input tree contains a single node.) On a more technical
side, reconstructing a multidirectional path that consists of two paths that share the same origin,
is more involved than reconstructing single paths. The former requires finding the lowest common
ancestor of the two randomly chosen nodes (Algorithm 3) as well as finding the root of the tree
(Algorithm 4.)
In our main Algorithm 1, finding out the bag of a particular node with respect to a directed
path is relatively easier than with respect to a multidirectional path. Note that by Lemma 1, a
multidirectional path is either a directed path, or two directed paths that share the same origin
(i.e., the lowest common ancestor.) In Algorithm 1, we simplify the bag assignment task, by
splitting a multidirected path (that is not a single path) into its two constituent directed paths.
The algorithm first recovers the lowest common ancestor, and then breaks the multidirectional
5

path into two paths. For instance, the multidirectional path 1, 2, 3, 4, 5 in Figure 3(d) with lowest
common ancestor 3 would become two paths 3, 2, 1 and 3, 4, 5.
Next, we explain each subroutine used in our main Algorithm 1. The first key step is to
recover the multidirectional path between two randomly chosen nodes. Algorithm 2 recovers the
sequence of nodes in the multidirectional path between any two nodes.
The idea behind Algorithm 2 is as follows. Let i, j ∈ V be two arbitrary nodes in the directed
rooted tree T = (V, E). Recall that some multidirectional paths are a single directed path. We
can easily detect this case by asking whether there is a path from i to j (i.e., whether Q(i, j) = 1),
or whether there is a path from j to i (i.e., whether Q(j, i) = 1.) Without loss of generalization,
assume there is a path in the directed rooted tree T from i to j. (We could similarly assume
that there is a path from j to i.) We can find out the set of all nodes {x1 , x2 , . . . xk } on the path
from i to j, by using path queries. For all nodes k ∈ V − {i, j}, we ask the oracle about Q(i, k)
and Q(k, j). Note that k is on the path from i to j, if and only if Q(i, k) = Q(k, j) = 1. After
finding out the set of all nodes {x1 , x2 , . . . xk } on the path from i to j, it remains to sort the
nodes in order to obtain the correct sequence, thus recovering the path. We sort the list of nodes
{i, x1 , x2 , . . . xk , j} by using the order relation given in Definition 5.
Some multidirectional paths consist of two directed paths that share the same origin m. In
this case, Algorithm 2 first recovers the lowest common ancestor m and then reconstructs two
directed paths: one from m to i, and one from m to j, by following the approach explained before.
In Algorithm 2, reconstructing a multidirectional path that consists of two paths requires finding
the lowest common ancestor of the two randomly chosen nodes. Our Algorithm 3 finds the lowest
common ancestor of a multidirectional path between any two arbitrary nodes.
Algorithm 3 works as follows. Let i, j ∈ V be two arbitrary nodes of the directed rooted tree
T = (V, E). First, we recover the directed path from the root to i. We assume that the order of
the nodes in the above path follow the order relation given in Definition 5. Thus, the tree root is
the first element on such path. Then, we iterate through all nodes in the path, in order to find
the last ancestor of j in the path from the root. This last ancestor is indeed the lowest common
ancestor of i and j. In Algorithm 3, in order to find the lowest common ancestor, one has to
find the root of the directed tree. Our Algorithm 4 identifies the path from the root to a given
arbitrary node.
The inner workings of Algorithm 4 are as follows. Let i ∈ V be an arbitrary node in the
directed rooted tree T = (V, E). For each node j ∈ V − {i}, we ask the oracle about Q(j, i). If
Q(j, i) = 1 then there is a path from j to i, and therefore we add node j to the list of nodes that
reach i. In order to recover the directed path from the root to i, we sort the aforementioned list
of nodes, by using the order relation given in Definition 5. That is, the first element on the sorted
list is the tree root.
The second key step in our main Algorithm 1 is to divide the nodes (which are not in the
multidirectional path) into bags defined by the multidirectional path. As argued before, if the
multidirectional path consists of two directed paths, then Algorithm 1 breaks the multidirectional
path into its two constituent directed paths, by using the least common ancestor. Thus, the bag
assigment task needs only to consider directed paths, as we do in Algorithm 5.
Here we give an intuitive explanation of the bag assignment task in Algorithm 5. For instance,
consider finding out the bag of node 10 in the directed path 1, 2, 3, 4, 5 in Figure 3(a). We see
that nodes 1, 2 and 3 are all ancestors of node 10 (i.e., Q(1, 10) = Q(2, 10) = Q(3, 10) = 1.) We
also see that nodes 4 and 5 are not ancestors of node 10 (i.e., Q(4, 10) = Q(5, 10) = 0.) Note that
node 10 belongs to the bag of node 3. The above suggests that the task of finding out the bag
of node 10 can be done by searching for a node i for which Q(i, 10) = 1 and Q(j, 10) = 0 where
(i, j) is an edge in the path. This can be efficiently done by performing binary search.
6

There are two exceptions to the above rule: when queries for all nodes in the path return
1, and when queries for all nodes in the path return 0. As an example for the first case (when
all queries return 1), consider finding out the bag of node 11 in the directed path 1, 2, 3, 4, 5 in
Figure 3(a). We see that nodes 1, 2, 3, 4 and 5 are all ancestors of node 11 (i.e., Q(1, 11) =
Q(2, 11) = Q(3, 11) = Q(4, 11) = Q(5, 11) = 1.) In this case, we assign node 11 to the bag of
the last node in the path, i.e., 5. As an example for the second case (when all queries return 0),
consider finding out the bag of node 10 in the directed path 3, 4, 5 in Figure 3(d). We see that
neither nodes 3, 4 or 5 are ancestors of node 10 (i.e., Q(3, 10) = Q(4, 10) = Q(5, 10) = 0.) In this
case, we assign node 10 to the bag of the lowest common ancestor, i.e., 3. Fortunately, all the
cases analyzed above are naturally handled by binary search.
The final step in our main Algorithm 1 is to cut the tree through the even separator, which
splits the tree into two subtrees. Our Algorithm 6 splits a directed rooted tree into two subtrees,
by cutting the original tree through any arbitrary edge.
The idea behind Algorithm 6 is as follows. Let e = (i, j) ∈ E be an arbitrary edge in the
directed rooted tree T = (V, E). Let T1 and T2 be two subtrees that result from removing e from
T . Note that every node must belong to either T1 or T2 . Without loss of generality, let i ∈ T1 and
j ∈ T2 . Since T is a directed rooted tree, j has one parent in T , which is indeed i. Removing (i, j)
from T makes j have no parents in T2 . Therefore, j is the root of T2 . For all nodes k ∈ V − {j},
we ask the oracle about Q(j, k). If Q(j, k) = 1, then k belongs to T2 , otherwise k belongs to T1 .
We finish the section by analyzing the time complexity of our randomized algorithm.
Theorem 1. Algorithm 1 takes O(dn log2 n) expected time, in order to reconstruct a directed
rooted tree of n nodes and node degree at most d. Furthermore, for a fixed probability of error
δ ∈ (0, 1), Algorithm 1 takes at most O( 1δ dn log2 n) time, with probability at least 1 − δ.
(See Appendix B for detailed proofs.)

4

Lower Bound and Extensions

In this section, we study lower bounds for reconstructing directed rooted trees from path queries.
We also extend our original algorithm for the case of noisy queries, as well as the reconstruction
of weighted trees from additive queries. Finally, we provide negative results for directed acyclic
graphs that provide some motivation for our assumptions.

4.1

Lower Bounds

Here, we present lower bounds for reconstructing directed rooted trees from path queries.
Theorem 2. In order to reconstruct a directed rooted tree of n nodes and node degree at most d,
any randomized algorithm requires at least Ω((1 − δ) n log n) queries, otherwise it would fail with
probability at least δ.
Theorem 3. In order to reconstruct a directed rooted tree of n nodes and node degree at most d,
any deterministic algorithm requires at least Ω(dn) queries.
Given the above results and Theorem 1, our algorithm is only a factor of O(d log n) from the
lower bound for any randomized algorithm, and a factor of O(log2 n) from the lower bound for any
deterministic algorithm. Both of these factors are small when compared to the time complexity
of our algorithm, which is O(dn log2 n).

7

4.2

Noisy Queries

Here, we analyze a noisy regime, in which the bit that represents the oracle’s answer gets flipped
with some probability, by an adversary, before it is revealed to the algorithm. Next, we formally
define noisy queries.
Definition 6. Let G = (V, E) be a directed acyclic graph, and let QG be a path query. A noisy
e G : V × V → {0, 1} such that
path query with noise parameter ε ∈ (0, 1/2) is a function Q
e G (i, j) = QG (i, j) with probability 1 − ε, and Q
e G (i, j) = 1 − QG (i, j) with probability ε.
Q
In order to make use of our original algorithm, we proceed with the following strategy. Algorithm 7 works as follows. For each node pair, we will perform majority voting on m noisy path
queries. If m is large enough, noise will be removed with high probability. (See Appendix A for
details.)
The above opens up a question on the number of queries m per node pair, that are sufficient
to guarantee graph recovery success. A second question is whether m depends on the number
of nodes n and maximum node degree d, thus affecting the time complexity of our randomized
algorithm. The following theorem answers both questions.
Theorem 4. For a fixed probability of error δ ∈ (0, 1) and noise parameter ε ∈ (0, 1/2), Algo2
1
1
rithm 7 takes at most O( 1δ (1/2−ε)
2 dn log n(log d + log n + log δ )) time, with probability at least
1 − δ, in order to reconstruct a directed rooted tree of n nodes and node degree at most d, provided
1
1
that the number of queries per node pair fulfills m ∈ Θ( (1/2−ε)
2 (log d + log n + log δ )).
In practice we do not need to know the exact value of the noise parameter ε. A lower bound
of ε suffices to define the number of queries m per node pair.

4.3

Additive Queries on Weighted Trees

Here, we focus on the reconstruction of weighted directed rooted trees by using additive queries.
An additive path query returns the sum of the edge weights on the directed path between two
given nodes, if such a path exists, or zero otherwise. Next, we formally define additive path
queries.
Definition 7. Let T = (V, E, W ) be a weighted directed rooted tree, with positive weights for each
edge, i.e., wi,j > 0 for all (i, j) ∈ E, and wi,j = 0 for all (i, j) ∈
/ E. An additive path query is a
b
b T (i, j) is
function QT : V × V → [0, +∞) such that if there exists a path in T from i to j then Q
b
the sum of the weights of the edges in the path, and QT (i, j) = 0 otherwise.
Note that the above query reveals much more information compared to the path query in
Definition 1 which only reveals a single bit of information. In Algorithm 8, our strategy is
to convert the additive query problem into our original problem for recovering the edge set.
Afterwards, we recover the edge weights by calling the additive queries for each edge. (See
Appendix A for details.)
The time complexity of the above algorithm is as follows.
Theorem 5. Algorithm 8 takes O(dn log2 n) expected time, in order to reconstruct a weighted
directed rooted tree of n nodes and node degree at most d. Furthermore, for a fixed probability of
error δ ∈ (0, 1), Algorithm 8 takes at most O( 1δ dn log2 n) time, with probability at least 1 − δ.

8

1
2

1
3

2

3

Figure 5: Two directed acyclic graphs that produce the same answers when using path queries.

4.4

Negative Results for Directed Acyclic Graphs

As argued before, the cost of asking queries is very high in several application domains. Thus,
we are interested on the reconstruction of graphs that do not require the trivial n2 queries for
n nodes (i.e., one query for every possible pair of nodes.) A natural question is whether more
general directed acyclic graphs could be recovered efficiently by asking less than Ω(n2 ) queries.
Here, we provide a negative answer for the above.
First note that some directed acyclic graphs are non-identifiable by using path queries. For
instance, consider the two graphs shown in Figure 5. In both graphs, we have that Q(1, 2) =
Q(2, 3) = Q(1, 3) = 1. Thus, by using path queries, it is impossible to discern whether the edge
(1, 3) exists or not. Next, we formalize the above intuition.
Definition 8. Let G = (V, E) be a directed acyclic graph. We say that an edge (i, j) ∈ E is
transitive if there exists a directed path from i to j of length greater than 1.
In Figure 5, edge (1, 3) is transitive, since there is a directed path 1, 2, 3 (i.e., a directed path
of length 2.) Transitive edges are not possible to be recovered by using path queries for the
following reason. Let i and j be two fixed nodes. Assume there is a directed path from i to j of
length greater than 1. Due to this path, we have that Q(i, j) = 1, regardless of whether (i, j) ∈ E
or (i, j) ∈
/ E. A trivial algorithm for reconstructing directed acyclic graphs of n nodes, without
transitive edges, is to ask n2 queries (i.e., one query for every possible pair of nodes.) Next, we
show that this trivial algorithm is indeed optimal.
Theorem 6. In order to reconstruct a directed acyclic graph of n nodes, without transitive
edges, any deterministic algorithm requires at least Ω(n2 ) queries. Furthermore, any randomized
algorithm requires at least Ω((1 − δ) n2 ), otherwise it would fail with probability at least δ.
Recall that our algorithm pertains to directed rooted trees with a maximum node degree.
These graphs are not only sparse but also weakly connected (i.e., their undirected skeleton graphs
are connected.) One could ask whether connectedness is a necessary condition, and whether sparsity makes graph reconstruction easier. Next, we show that an algorithm requires Ω(n2 ) queries
for recovering a family of sparse disconnected graphs, as well as a family of sparse connected
graphs.
Theorem 7. In order to reconstruct a sparse disconnected directed acyclic graph of n nodes, any
deterministic algorithm requires at least Ω(n2 ) queries.
Theorem 8. In order to reconstruct a sparse connected directed acyclic graph of n nodes, any
deterministic algorithm requires at least Ω(n2 ) queries.

5

Concluding Remarks

There are several ways of extending this research. The analysis of the reconstruction of other
families of graphs in O(n log n) time would be of great interest. Given our results for directed
rooted trees, it would be interesting to analyze other families of sparse connected graphs, such as
graphs with bounded tree-width as well as graphs with bounded arboricity.
9

References
[1] Mohamad Akra and Louay Bazzi. On the solution of linear recurrence equations. Computational Optimization and Applications, 10(2):195–210, 1998.
[2] Noga Alon and Vera Asodi. Learning a hidden subgraph. International Colloquium on
Automata, Languages and Programming, Lecture Notes in Computer Science, 3142:110–121,
2004.
[3] Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a
hidden matching. SIAM Journal on Computing, 33(2):487–501, 2004.
[4] Dana Angluin and Jiang Chen. Learning a hidden graph using O(log n) queries per edge.
Conference on Learning Theory, pages 210–223, 2004.
[5] Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann,
Matúš Mihal’ák, and L. Shankar Ram. Network discovery and verification. IEEE Journal
on Selected Areas in Communications, 24(12):2168–2181, 2006.
[6] Sung-Soon Choi. Polynomial time optimal query algorithms for finding graphs with arbitrary
real weights. Conference on Learning Theory, pages 1–22, 2013.
[7] Fan Chung. Separator theorems and their applications. Paths, Flows, and VLSI-Layout,
pages 17–34, 1990.
[8] Thomas Cover and Joy Thomas. Elements of Information Theory. John Wiley & Sons, 2nd
edition, 2006.
[9] Joseph Culberson and Piotr Rudnicki. A fast algorithm for reconstructing trees from distance
matrices. Information Processing Letters, 30(4):215–220, 1989.
[10] Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the
additive model. Algorithmica, 28(1):104–124, 2000.
[11] Jotun Hein. An optimal algorithm to reconstruct trees from additive distance data. Bulletin
of Mathematical Biology, 51(5):597–603, 1989.
[12] M. Jagadish and Anindya Sen. Learning a bounded-degree tree using separator queries.
Algorithmic Learning Theory, Lecture Notes in Computer Science, 8139:188–202, 2013.
[13] Hanna Mazzawi. Optimally reconstructing weighted graphs using queries. ACM-SIAM
Symposium on Discrete Algorithms, pages 608–615, 2010.
[14] Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on
edge counting. Algorithmic Learning Theory, Lecture Notes in Computer Science, 4754:285–
297, 2007.

10

A

Detailed Algorithms

In this section, we show the pseudocode for all the algorithms in our manuscript. First, we present
our main Algorithm 1 for reconstructing a directed rooted tree by using path queries.
Algorithm 1 Reconstruct tree
1: Input: vertex set V of the directed rooted tree T
2: if |V | = 1 then
3:
E←∅
4: else
5:
while true do
6:
Pick i, j ∈ V independently and uniformly at random
7:
(multidirpath, lowestancestoridx) ← Reconstruct multidirectional path(V, i, j)
8:
Assume multidirpath = [x1 , . . . , xP ]
9:
pathleft ← reverse(multidirpath[1 to lowestancestoridx])
10:
pathright ← multidirpath[lowestancestoridx to P ]
11:
bagsize ← [1, . . . , 1], an array of size P
12:
for each node k that is not on multidirpath do
13:
bagidxleft ← Find bag(pathleft, k)
14:
bagidxright ← Find bag(pathright, k)
15:
if bagidxleft = lowestancestoridx then
16:
bagidx ← bagidxright + length(pathleft) − 1
17:
else
18:
bagidx ← bagidxleft
19:
end if
20:
bagsize[bagidx] ← bagsize[bagidx] + 1
21:
end for
22:
leftsize ← 0
23:
evenseparator ← None
24:
for r = 1, . . . , P − 1 do
25:
leftsize ← leftsize + bagsize[r]
26:
if leftsize ∈ [n/d, (d − 1)n/d] then
27:
evenseparator ← (xr , xr+1 )
28:
break
29:
end if
30:
end for
31:
if evenseparator 6= None then
32:
break
33:
end if
34:
end while
35:
(V1 , V2 ) ← Split tree(V , evenseparator)
36:
E1 ← Reconstruct tree(V1 )
37:
E2 ← Reconstruct tree(V2 )
38:
E ← E1 ∪ E2 ∪ { evenseparator }
39: end if
40: Output: edge set E
Next, we present Algorithm 2 for recovering the sequence of nodes in the multidirectional
11

path between any two nodes.
Algorithm 2 Reconstruct multidirectional path
1: Input: vertex set V of the directed rooted tree T , two nodes i, j ∈ V
2: multidirpath = [], lowestancestoridx = None
3: if Q(i, j) = 1 then
4:
for each node k ∈ V − {i, j} where Q(i, k) = 1 and Q(k, j) = 1 do
5:
multidirpath ← append(multidirpath, k)
6:
end for
7:
Sort multidirpath with the order relation given in Definition 5
8:
multidirpath ← append(i, multidirpath, j)
9:
lowestancestoridx ← 1
10: else if Q(j, i) = 1 then
11:
for each node k ∈ V − {i, j} where Q(j, k) = 1 and Q(k, i) = 1 do
12:
multidirpath ← append(multidirpath, k)
13:
end for
14:
Sort multidirpath with the order relation given in Definition 5
15:
multidirpath ← append(j, multidirpath, i)
16:
lowestancestoridx ← 1
17: else
18:
m ← Find lowest common ancestor(V, i, j)
19:
pathleft ← [], pathright ← []
20:
for each node k ∈ V − {m, i} where Q(m, k) = 1 and Q(k, i) = 1 do
21:
pathleft ← append(pathleft, k)
22:
end for
23:
Sort pathleft with the order relation given in Definition 5
24:
for each node k ∈ V − {m, j} where Q(m, k) = 1 and Q(k, j) = 1 do
25:
pathright ← append(pathright, k)
26:
end for
27:
Sort pathright with the order relation given in Definition 5
28:
multidirpath ← append(i, reverse(pathleft), m, pathright, j)
29:
lowestancestoridx ← 2+length(pathleft)
30: end if
31: Output: multidirpath, lowestancestoridx
In what follows, we present Algorithm 3 for finding the lowest common ancestor of a multidirectional path between any two arbitrary nodes.

12

Algorithm 3 Find lowest common ancestor
1: Input: vertex set V of the directed rooted tree T , two nodes i, j ∈ V
2: pathfromroot ← Find path from root(V , i)
3: for each node k in pathfromroot do
4:
if Q(k, j) = 1 then
5:
lowestcommonancestor ← k
6:
break
7:
end if
8: end for
9: Output: lowestcommonancestor
Next, we present Algorithm 4 for identifying the path from the root to a given arbitrary node.
Algorithm 4 Find path from root
1: Input: vertex set V of the directed rooted tree T , node i ∈ V
2: pathfromroot ← []
3: for each node j ∈ V − {i} do
4:
if Q(j, i) = 1 then
5:
pathfromroot ← append(pathfromroot, j)
6:
end if
7: end for
8: Sort pathfromroot with the order relation given in Definition 5
9: Output: pathfromroot
Next, we present Algorithm 5 for finding out the bag of a node with respect to an arbitrary
directed path.
Algorithm 5 Find bag
1: Input: path x1 , x2 , . . . , xk , node i ∈ V where V is the vertex set of the directed rooted tree
T
2: l ← 1, r ← k
3: while l < r do
4:
m ← (l + r)/2
5:
if Q(xm , i) = 1 then
6:
l←m
7:
else
8:
r←m
9:
end if
10: end while
11: Output: bag index l ∈ {1, . . . , k}
In what follows, we present Algorithm 6 for splitting a directed rooted tree into two subtrees,
by cutting the original tree through any arbitrary edge.

13

Algorithm 6 Split tree
1: Input: vertex set V of the directed rooted tree T = (V, E), edge (i, j) ∈ E
2: V1 ← ∅, V2 ← {j}
3: for each node k ∈ V − {j} do
4:
if Q(j, k) = 1 then
5:
V2 ← V2 ∪ {k}
6:
else
7:
V1 ← V1 ∪ {k}
8:
end if
9: end for
10: Output: partitions V1 , V2 of V
Next, we present Algorithm 7 for reconstructing a directed rooted tree by using noisy path
e (k) (i, j) to denote the k-th call to the query Q
e T (i, j), since for our problem,
queries. We will use Q
the directed rooted tree T is fixed (but unknown).
Algorithm 7 Reconstruct tree from noisy queries
1: Input: vertex set V of the directed rooted tree T , number of queries m per node pair
Pm e (k)
0
2: Define the path query Q0 as follows. Let Q0 (i, j) = 1 if
k=1 Q (i, j) > m/2, and Q (i, j) = 0
otherwise.
3: E ← Reconstruct tree(V )
4: Output: edge set E
Finally, we present Algorithm 8 for reconstructing a weighted directed rooted tree by using
b j) to denote Q
b T (i, j) since for our problem, the weighted
additive path queries. We will use Q(i,
directed rooted tree T is fixed (but unknown).
Algorithm 8 Reconstruct weighted tree from additive queries
1: Input: vertex set V of the weighted directed rooted tree T
b j) > 0, and Q(i, j) = 0 otherwise.
2: Define the path query Q as follows. Let Q(i, j) = 1 if Q(i,
3: E ← Reconstruct tree(V )
4: W ← 0
5: for each edge (i, j) ∈ E do
b j)
6:
wi,j = Q(i,
7: end for
8: Output: edge set E, edge weights W

B

Detailed Proofs

In this section, we state the proofs of all the theorems and lemmas in our manuscript.

B.1

Proof of Lemma 1

Proof. Existence and uniqueness follows straightforwardly from the fact that the directed rooted
tree T is weakly connected (i.e., the undirected skeleton graph of T is connected.) For the second
claim, note that each node in T = (V, E) has at most one parent. Given any three different nodes

14

p, q, r ∈ V , the following condition holds ¬((p, r) ∈ E ∧ (q, r) ∈ E). Thus, we can only construct
the three cases provided in the statement, otherwise we would violate the latter condition.

B.2

Proof of Theorem 1

Proof. Let a “round” be a repetition of the “while” loop at Line 5 of Algorithm 1. We show that
there are O(d) rounds in expectation, and that each round takes O(n log n) time. We then finish
the proof by the application of the master theorem.
First, we analyze the expected number of rounds for finding an even separator in the multidirectional path between two nodes chosen independently and uniformly at random. Recall that
by Lemma 1 for directed rooted trees, a multidirectional path between any two arbitrary nodes
always exists and is unique. Thus, it remains to analyze the probability that two randomly chosen
nodes lie on a different subtree defined by the even separator.
Recall that Corollary 2.3 in [7] shows if the tree T has node degree at most d, then an even
separator exists. More specifically, from Definition 3, we know the even separator splits the tree
into two subtrees, where each of the subtrees have a number of nodes between n/d and (d−1)n/d.
Next, we reason about the two randomly selected nodes on each round. Let q be the proportion
of nodes on the first subtree, and 1 − q be the proportion of nodes on the second subtree. We
know that q ∈ [1/d, (d − 1)/d] and similarly 1 − q ∈ [1/d, (d − 1)/d]. Since both nodes are selected
independently and uniformly at random from the set of n nodes, then q 2 is the probability that
both nodes fall in the first subtree. Similarly, (1 − q)2 is the probability that both nodes fall in
the second subtree. The probability p that the two nodes lie on a different subtree is

p≥
min
1 − q 2 − (1 − q)2
q∈[1/d,(d−1)/d]

= 1 − (1/d)2 − ((d − 1)/d)2
= 2(d − 1)/d2
∈ Ω(1/d) .
Therefore, the expected
rounds r until we successfully find two nodes lying on a different
P∞ number of
r−1
subtree is E[r] = r=1 r(1 − p) p = 1/p which is O(d). We now show that each round takes
O(n log n) time. First, we derive a sequence of conclusions regarding the subroutines:
• Algorithm 4 takes O(n log n) time, since the most time-consuming step is sorting in Line 8.
• Algorithm 3 takes O(n log n) time, since the most time-consuming step is the call to Algorithm 4 in Line 2, which takes O(n log n) time.
• Algorithm 2 takes O(n log n) time, since the most time-consuming steps are sorting in
Lines 7, 14, 23 and 27, and the call to Algorithm 3 in Line 18, which takes O(n log n) time.
• Algorithm 5 takes O(log n) time, since it performs binary search.
• Algorithm 6 takes O(n) time, since the “for” loop in Line 3 iterates for at most n times.
Recall that each round calls Algorithms 2, 5 and 6. It can be observed then, that the most
time-consuming step on each round is the call to Algorithm 2, which takes O(n log n) time.
Thus, so far we know that the time complexity of the “while” loop at Line 5 is O(dn log n).
To finalize the proof, note that Algorithm 1 exits the “while” loop at Line 5 when it finds an
even separator. Recall from Definition 3 that the even separator splits the tree into two subtrees,
15

where each of the subtrees have a number of nodes between n/d and (d−1)n/d. The total running
time for Algorithm 1 is given by the recursive formula
C(n) = C(n/d) + C((d − 1)n/d) + O(dn log n) .
For clarity, we rewrite C(n) in terms of the master theorem in [1]. That is, C(n) = α1 C(β1 n) +
α2 C(β2 n) + γ(n), for α1 = α2 = 1, β1 = 1/d, β2 = (d − 1)/d
∈ O(dn log n). By invoking
R n and γ(n)
s
s+1
the master theorem in [1], we have that C(n) ∈ O(n 1 γ(z)/z dz), where s is the value for
which α1 β1s + α2 β2s = 1. In our case s = 1 and thus C(n) ∈ O(dn log2 n).
For the remainder of the proof, we will use C to denote C(n) since n is a constant. Note
that C is a non-negative random variable with expectation E[C] ∈ O(dn log2 n). By Markov’s
inequality, we have that P[C > a] ≤ E[C]/a. By letting a = E[C]/δ we have P[C > E[C]/δ] ≤ δ.
Therefore P[C ≤ E[C]/δ] ≥ 1 − δ, and we prove our claim that P[C ∈ O( 1δ dn log2 n)] ≥ 1 − δ.

B.3

Proof of Theorem 2

Proof. Here we provide an information-theoretic lower bound for any randomized algorithm, based
on Fano’s inequality [8].
Let Tn,d be the set of directed rooted trees of n nodes and node degree at most d. Next,
we show that log |Tn,d | ∈ Θ(n log n). Interestingly, the latter (tight) bound does not depend on
d. For a lower bound, note that the number of directed rooted trees with at most one children
is equal to the number of permutations of n nodes, which is n!. We have log |Tn,d | ≥ log n! ≥
n(log n − 1) ≥ 41 n log n for n ≥ 4 and therefore log |Tn,d | ∈ Ω(n log n). For an upper bound,
note that the number of directed rooted trees with no constraint in the number of children is
equal to the number of directed spanning trees, which is nn−1 by Cayley’s formula. We have
log |Tn,d | ≤ log nn−1 ≤ n log n and therefore log |Tn,d | ∈ O(n log n). From the above, we conclude
that log |Tn,d | ∈ Θ(n log n).
Assume that nature picks a directed rooted tree T ∗ ∈ Tn,d uniformly at random. Any mechanism for finding out the correct tree is allowed to make C possibly-dependent queries (for C
node pairs) for which the binary responses are Q1 , . . . , QC . Let T ∈ Tn,d be the directed rooted
tree that is guessed on the basis of the C query responses. The above defines a Markov chain
T ∗ → (Q1 , . . . , QC ) → T .
By properties of the mutual information, and since the joint responses (Q1 , . . . , QC ) can take
up to 2C possible values, we have:
I(T ∗ ; Q1 , . . . , QC ) ≤ H(Q1 , . . . , QC )
≤ C log 2 .
By the Fano’s inequality [8] on the Markov chain T ∗ → (Q1 , . . . , QC ) → T we have
I(T ∗ ; Q1 , . . . , QC ) + log 2
log |Tn,d |
C log 2 + log 2
≥1−
n(log n − 1)
≡δ.

P[T 6= T ∗ ] ≥ 1 −

By solving for C, we have that if C ≤ (1 − δ) n(log n − 1)/ log 2 − 1 then P[T 6= T ∗ ] ≥ δ and we
prove our claim.

16

B.4

Proof of Theorem 3

Proof. The proof relies on constructing a family of “parallel-chain” trees. We assume that the
algorithm knows that the directed rooted tree to be reconstructed is “parallel-chain”. We also
assume that the algorithm has additional side information (described later for clarity.)
Assume that n − 1 is divisible by d, and let k = n−1
d . Assume the node set V is partitioned
into k + 1 fixed sets V0 , V1 , . . . , Vk , such that |V0 | = 1 and |Vl | = d for l = 1, . . . , k. We then create
a tree T = (V, E) with kd edges such that: the single node in V0 has d children (each node in V1 ),
n − d − 1 nodes have one child (each node in Vl has one children in Vl+1 for l = 1, . . . , k − 1), and
the remaining d nodes (in Vk ) are leaves. The above creates a “parallel-chain” directed rooted
tree as shown in Figure 6.
V0
V1
V2
V3
d = 4 “branches”
Figure 6: A “parallel-chain” directed rooted tree.
Moreover, we assume that the algorithm also knows the node sets V0 , V1 , . . . , Vk . What remains
to be recovered is the “branch” (from 1 to d) to which the nodes in V1 , . . . , Vk belong to. In order
to do this, the algorithm has to ask a query Q(i, j) for each i ∈ Vl , j ∈ Vl+1 and l = 1, . . . , k − 1.
dn
2
The total number of queries is (k−1)d2 = ( n−1
d −1)d ≥ 2 for n ≥ 2(d+1). Thus, a deterministic
dn
algorithm requires at least 2 queries.

B.5

Proof of Theorem 4

Proof. Our first goal is to find the condition for which the path query Q is equal to its noisy
approximation Q0 . We start by making some observations for a single fixed node pair (i, j) and
later extends our observations for several node
pairs.
1 Pm
e (k)
Define the random variable R(i, j) ≡ m
k=1 Q (i, j). Recall that we defined the path query
0
0
Q as follows. Let Q (i, j) = 1 if R(i, j) > 1/2, and Q0 (i, j) = 0 otherwise.
e (k) (i, j) = 1 with probability 1 − ε,
Assume that Q(i, j) = 1. By Definition 6, we have that Q
(k)
(k)
e (i, j) = 0 with probability ε. Clearly, E[Q
e (i, j)] = 1−ε and therefore E[R(i, j)] = 1−ε.
and Q
By using Hoeffding’s inequality, we have
P[Q(i, j) 6= Q0 (i, j)] = P[R(i, j) < 1/2]
= P[R(i, j) − E[R(i, j)] < 1/2 − E[R(i, j)]]
= P[R(i, j) − E[R(i, j)] < ε − 1/2]
2

≤ e−2m(1/2−ε) .
e (k) (i, j) = 0 with probability
Now assume that Q(i, j) = 0. By Definition 6, we have that Q
e (k) (i, j) = 1 with probability ε. Clearly, E[Q
e (k) (i, j)] = ε and therefore E[R(i, j)] = ε.
1 − ε, and Q
17

By using Hoeffding’s inequality, we have
P[Q(i, j) 6= Q0 (i, j)] = P[R(i, j) > 1/2]
= P[R(i, j) − E[R(i, j)] > 1/2 − E[R(i, j)]]
= P[R(i, j) − E[R(i, j)] > 1/2 − ε]
2

≤ e−2m(1/2−ε) .
Assume that Algorithm 1 in Line 3 of Algorithm 7 makes C path queries. That is, assume
that queries were made for C node pairs (i1 , j1 ), (i2 , j2 ), . . . , (iC , jC ). By the union bound and
the previous observations, we have:
P[(∃k = 1, . . . , C) Q(ik , jk ) 6= Q0 (ik , jk )] ≤ Ce−2m(1/2−ε)

2

≡ δ/2 .
By solving for m, we have that if m ≥

1
2(1/2−ε)2

(log C + log 2δ ) then

P[(∀k = 1, . . . , C) Q(ik , jk ) = Q0 (ik , jk )] ≥ 1 − δ/2 .
That is, with probability at least 1 − δ/2, the path query Q is equal to its noisy approximation
Q0 and thus Algorithm 7 reconstructs the tree T correctly, provided that m is large enough.
By Theorem 1, with probability at least 1 − δ/2, we have that C ∈ O( 2δ dn log2 n). From the
1
1
1
2
above, we have that m ∈ Θ( (1/2−ε)
2 (log d + log n + log δ )) fulfills m ≥ 2(1/2−ε)2 (log C + log δ ).
Finally, the total number of queries is given by Cm ∈ O( 1δ
and we prove our claim.

B.6

1
(1/2−ε)2

dn log2 n(log d + log n + log 1δ ))

Proof of Theorem 5

Proof. Straightforwardly, by the fact that the most time-consuming step in Algorithm 8 is the
call to Algorithm 1 in Line 3, and by the result in Theorem 1.

B.7

Proof of Theorem 6

Proof. Let Gn be the set of directed acyclic graphs of n nodes, without transitive edges. Next, we
show that log |Gn | ∈ Θ(n2 ). For a lower bound, we focus on a particular class of “two-layered”
graphs. First, the node set V = {1, . . . , n} is partitioned into two sets V1 = {1, . . . , bn/2c} and
V2 = {bn/2c + 1, . . . , n}. We then allow only for edges from nodes in V1 to nodes in V2 . That is,
each node in V2 can have as parents any subset of the nodes in V1 , thus, there are 2|V1 | choices of
edge sets for each of the |V2 | nodes in V2 . We have log |Gn | ≥ log 2|V1 ||V2 | = log 2bn/2c(n−bn/2c) ≥
log 2n(n−1)/4 ≥ log5 2 n2 for n ≥ 5 and therefore log |Gn | ∈ Ω(n2 ). For an upper bound, note
that the number of directed acyclic graphs (without transitive edges) is less than the number of
n
directed graphs of n nodes, which is 3( 2 ) . This follows from the fact that for any two nodes i
and j, we have three cases in a directed graph G = (V, E). Either (i, j) ∈ E, or (j, i) ∈ E or
n
{(i, j), (j, i)} 6⊂ E. Now, we have log |Gn | ≤ log 3( 2 ) ≤ log2 3 n2 and therefore log |Gn | ∈ O(n2 ).
From the above, we conclude that log |Gn | ∈ Θ(n2 ).
Since each query only reveals a single bit of information, the lower bound of Θ(n2 ) for any
deterministic algorithm follows.
For the lower bound for any randomized algorithm, we proceed as in Theorem 2 by using
Fano’s inequality [8].
18

B.8

Proof of Theorem 7

Proof. The proof relies on constructing a family of graphs with a single edge. We assume that
the algorithm knows that the directed acyclic graph to be reconstructed has a single edge.
Assume two fixed nodes i, j ∈ V . The directed graph to be reconstructed is G = (V, E) where
E = {(i, j)}. Note that Q(i, j) = 1. Furthermore Q(k, l) = 0 for every node pair (k, l) 6= (i, j).
That is only one query returns 1, while n2 − 1 queries return 0. Thus, a deterministic algorithm
does not obtain any information from the n2 − 1 queries in order to guess the edge (i, j), and
therefore it requires at least n2 queries in the worst case.

B.9

Proof of Theorem 8

Proof. The proof relies on constructing a family of “v-structured two-layered” graphs. We assume
that the algorithm only knows that the directed acyclic graph to be reconstructed has n − 1 edges
(i.e., the algorithm does not know that the graph is “v-structured two-layered”.)
Assume the node set V is partitioned into two fixed sets V1 and V2 . For simplicity assume that
there is an odd number of nodes, and that |V2 | = |V1 |+1. Thus, |V1 | = bn/2c and |V2 | = bn/2c+1.
We then create the graph G = (V, E) with n − 1 edges such that each node in V1 is the source of
2 edges, and each node in V2 is the target of at most 2 edges. The above creates a “v-structured
two-layered” graph as shown in Figure 7.
V1
V2
Figure 7: A “v-structured two-layered” directed acyclic graph.
Note that Q(i, j) = 1 for (i, j) ∈ E, while Q(i, j) = 0 for (i, j) ∈
/ E. That is only n − 1 queries
return 1, while n2 − n + 1 queries return 0. Thus, a deterministic algorithm does not obtain any
information from the n2 − n + 1 queries in order to guess the edge set E, and therefore it requires
at least n2 − n + 2 queries in the worst case. (Since the algorithm knows that there are n − 1
edges, it can stop asking queries as soon as the first bit 1 is returned.)

C

Experiments

In this section, we present our experimental validation. We performed 10 repetitions for different
number of nodes, and node degrees. For each repetition, we generate a random bounded-degree
directed rooted tree, in order to test whether our Algorithm 1 can successfully recover the tree by
using path queries, as well as to count the number of queries needed in practice. We experimentally
found that all trees were successfully recovered in practice. Thus, we focused on the question
regarding the number of queries needed by Algorithm 1 in practice.
Figure 8(a) shows the number of queries for different number of nodes, while Figure 8(b)
shows the number of queries for different node degrees. From our results, it can be observed that
the number of queries used by Algorithm 1 is less than what Theorem 1 predicted. Furthermore,
for a constant degree d, the experimental results are much better for a large number of nodes n,
as shown in Figure 8(a).

19

800000

700000

700000

600000

600000

Number of queries

Number of queries

800000

500000
400000
300000
200000
100000
00

500000
400000
300000
200000
100000

1000

2000

3000

Number of nodes n

4000

00

5000

(a)

100

200

300

400

Maximum node degree d

500

(b)

Figure 8: (a) Number of queries for different number of nodes n, for a maximum node degree
d = 5. (b) Number of queries for different node degrees d, for a number of nodes n = 1000. The
upper bound for the number of queries in Theorem 1 is shown in blue. The actual number of
queries used by Algorithm 1 is shown in red. (Error bars were computed for 10 repetitions, at
95% significance level.)

20

