<p><strong>No.</strong>  The following simple adversary strategy implies that any algorithm to reconstruct an $n$-node tree requires at least $\binom{n-1}{2} = n(n-1)/2$ "betweenness" queries.</p>

<p>Arbitrarily label the nodes $0,1,2,\dots,n-1$.  The adversary answers all queries as though the tree is a star with vertex $0$ in the center; think of $0$ as the root and the other nodes as its children.</p>

<pre><code>Between?(a,x,b)
    if x=0 return TRUE else return FALSE
</code></pre>

<p>Now suppose the algorithm halts after performing less than $n(n-1)/2$ queries.  Then there must be two vertices $y$ and $z$, neither equal to zero, such that the algorithm has not queried any permutation of the triple $(0,y,z)$.  If the algorithm claims that the tree is not a star with center $0$, the adversary reveals its input, proving the algorithm wrong.  The adversary then reveals that $x$ is actually the only child of $y$, proving the algorithm wrong again.</p>

<p><strong>Update:</strong> Oops, just noticed the degree constraint.  <strike>Fortunately, this is not a major hurdle.  Replace node $0$ with your favorite binary tree, with the other $n-1$ nodes as leaves in some unknown order, and then reveal this subtree to the reconstruction algorithm.  Reconstructing the resulting $(2n-3)$-node binary tree still requires at least $n(n-1)/2$ queries.  Equivalently, reconstructing an $m$-node binary tree requires at least $(m+3)(m+2)/8$ queries.  (I'm sure a more subtle construction would improve the constant.)</strike>  <b>As Jagadish points out, this generalization doesn't work; queries about internal nodes in the tree impose an ordering on the leaves, which reduced the number of necessary queries.</b></p>

CC BY-SA 3.0
2012-03-19T14:53:48.943Z
My question is about constant-degree trees. This argument doesn't work for that case, right?
Jagadish
CC BY-SA 3.0
2012-03-19T14:56:06.867Z
@Jagadish: Yes, the argument still works; see my update
Jeffε
CC BY-SA 3.0
2012-03-19T15:11:02.260Z
@Jeffe I don't understand the modification. Is the longest diameter among the graphs which the adversary keeps O(log n) then?
Jagadish
CC BY-SA 3.0
2012-03-19T15:19:31.483Z
Yes.  To put it more simply: The adversary has either a complete binary tree with depth $\lg n$, or a complete binary tree with one leaf removed and reinserted as a child of another leaf.
Jeffε
CC BY-SA 3.0
2012-03-19T15:21:42.047Z
@Jeffe You argument seems to imply Omega(n^2) bound for a randomized algorithm too...but there is an O(n log n) randomized algorithm for this case.
Jagadish
CC BY-SA 3.0
2012-03-19T15:29:09.167Z
If the diameter of the tree is D, then I have an algorithm that runs in O(nD log n), so your argument doesn't hold. In the star-graph case, the adversary had n^2 graphs to start with but in the modification that's not the case, right?
Jagadish
CC BY-SA 3.0
2012-03-19T15:37:02.073Z
@Jagadish: (1) I do not think that this proof of a lower bound works for randomized algorithms.  The adversary can still construct a failing example, but that does not contradict the hypothesis that the randomized algorithm works correctly with high probability.  (2) By the way, it seems that you asked the question knowing the answer.  What did you do that for?
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-19T15:51:25.560Z
@Jagadish: Oops, you're right; my argument for constant-degree trees is broken.  Queries about triples (a,x,b) where x is in the replacement tree reveal information about the left-to-right ordering of the leaves.
Jeffε
CC BY-SA 3.0
2012-03-19T15:53:04.437Z
@Jagadish: Do you have a reference for the randomized O(n log n)-time algorithm?  (Is that only for bounded-degree trees?)
Jeffε
CC BY-SA 3.0
2012-03-19T16:12:28.470Z
@JɛﬀE I'm not sure about $O(n \log n)$, but something like $O(n^{\log_2{3}})$ is possible (for bounded degree). Pick each vertex independently with probability 1/2, construct an induced tree recursively, then use its center as "pivot" to split the tree into 2 almost equal parts and construct them recursively (the split can be done in linear time with some technicality, if I am not mistaken). P.S. I mean, that's obviously $o(n^2)$ so the question sounds strange. +1 to JɛﬀE's comment.
Dmytro Korduban
CC BY-SA 3.0
2012-03-19T18:38:41.740Z
@JɛﬀE Pick two vertices randomly. With nearly 1/8 probability they will be leaves (since it is a complete binary tree with extra layer of leaves). So the median of the path connecting them will be the root. It takes O(n) expected time to label the root after which we recurse. So we get a O(n log n) randomized algorithm for this case.
Jagadish
CC BY-SA 3.0
2012-03-19T18:54:31.333Z
@Tsuyoshi I meant a randomized algorithm for the case when we know the tree to be an almost complete binary tree (JɛﬀE's construction). Sorry if my earlier comment looked like I knew a O(n log n) randomized algorithm for the actual problem.
Jagadish
CC BY-SA 3.0
2012-03-19T19:41:15.973Z
I see.  Thanks for the explanation, and also thanks for editing the question!
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-20T06:32:18.600Z
@JɛﬀE I think the above randomized algorithm can be modified to work for binary trees: Pick two vertices $x$ and $y$ randomly. With 1/9 probability they will lie on opposite sides of a separator. Pick the middle node of the path from $x$ to $y$. See if it is a good separator, if not do binary search. This takes $O(n \log n)$ expected time to find the separator. So we get a $O(n\;\log^2 n)$ randomized algorithm. Anyway, my question is about the deterministic case, so this probably doesn't say much..
Jagadish
CC BY-SA 3.0
2012-03-20T08:54:12.900Z
If you have a randomized algorithm, then you have an algorithm.  Determinism is overrated.
Jeffε
CC BY-SA 3.0
2012-03-20T13:34:28.097Z
I agree. But I'm unable to find an explicit deterministic algorithm.
Jagadish
CC BY-SA 3.0
2012-03-21T08:28:24.993Z
This problem reminds me of sorting/matching nuts and bolts.  A randomized algorithm that runs in $O(n \log n)$ time with high probability is easy — it's just [randomized quicksort](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-nutsbolts.pdf).  There is a deterministic $O(n\log n)$-time algorithm, but it is [seriously nontrivial](http://dl.acm.org/citation.cfm?id=296075).
Jeffε
CC BY-SA 3.0
2012-03-22T18:54:40.243Z
The previous work mentioned in that paper looks more readable. In Alon et.al's paper (which achieves $O(n\;\log^4 n)$-time) this sentence caught my eye: "The algorithm constructs `deterministic samples' by applying expander graphs in an interesting way." Finding the median nut is definitely harder than finding the median of $n$ numbers. So I'm wondering if there is a paper that explains how to find the median of $n$ numbers in  $o(n\;\log n)$ time using expander graphs.
Jagadish
CC BY-SA 3.0
2012-03-19T14:45:09.557Z
2012-03-19T15:49:42.613Z
2012-03-19T15:49:42.613Z
Jeffε
<p>Anindya Sen and I have a <a href="http://link.springer.com/chapter/10.1007%2F978-3-642-40935-6_14" rel="nofollow">paper</a> in ALT '13 where we give an $\tilde O(n \sqrt{n})$ algorithm for this problem. We don't know if a better algorithm is possible.</p>

CC BY-SA 3.0
2013-10-15T14:01:49.860Z
2016-05-30T04:21:23.393Z
2016-05-30T04:21:23.393Z
Jagadish
<p>Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?". Assume that each query can be answered in constant time by an oracle. We know the value of $n$, the number of nodes in the tree. The objective is to minimize the time taken to output the tree in terms of $n$.</p>

<p>Does there exist an $o(n^2)$ algorithm for the above problem?</p>

<p>Assume that the degree of any node in $T$ is at most 3.</p>

<hr>

<p><strong>What I know</strong></p>

<p><strong>Bounded diameter case is easy</strong>. If the diameter of the tree is $D$, then we can get a divide-and-conquer algorithm:</p>

<p>Any binary tree has a good separator that divides the tree into components of size no less than 1/3n.</p>

<ol>
<li>Pick any vertex x. If it is a good separator label that and recurse.</li>
<li>Find all the 3 neighbors of x. </li>
<li>Move in the direction of the neighbor which has the largest number of nodes. Repeat Step 2 with the neighbor.</li>
</ol>

<p>Since finding the separator takes at most $D$ steps, we get a $O(nD\log n)$ algorithm.</p>

<p><strong>An $O(n\;\log^2 n)$ randomized algorithm</strong>. (moved from comments below)</p>

<p>Pick two vertices x and y randomly. With 1/9 probability they will lie on the opposite sides of a separator. Pick the middle node of the path from $x$ to $y$. See if it is a separator, if not do binary search.</p>

<p>It takes $O(n\;\log n)$ expected time to find the separator. So we get a $O(n\;\log^2 n)$ randomized algorithm.</p>

<hr>

<p><i>Background. I learnt about this problem from a friend who works in probabilistic graphical models. The above problem roughly corresponds to learning the structure of a <a href="http://en.wikipedia.org/wiki/Tree_decomposition">junction tree</a> using an oracle which, given three random variables X,Y and Z, can tell the value of mutual information between X and Y given the value of Z. If the value is close to zero, we may assume that Z lies on the path from X to Y.</i></p>

CC BY-SA 3.0
2012-03-19T15:54:41.970Z
Please reveal what you already know about the problem, so we don't waste our time reinventing the wheel.
Jeffε
CC BY-SA 3.0
2012-03-19T18:17:02.207Z
@JɛﬀE I've edited my question.
Jagadish
<ds.algorithms><reference-request><graph-algorithms><oracles><query-complexity>
Reconstructing a tree from separator queries
Jagadish
# Reconstructing a tree from separator queries

(Asked by: username_0 on 2012-03-19)

Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?". Assume that each query can be answered in constant time by an oracle. We know the value of $n$, the number of nodes in the tree. The objective is to minimize the time taken to output the tree in terms of $n$.

Does there exist an $o(n^2)$ algorithm for the above problem?

Assume that the degree of any node in $T$ is at most 3.

---

**What I know**

**Bounded diameter case is easy**. If the diameter of the tree is $D$, then we can get a divide-and-conquer algorithm:

Any binary tree has a good separator that divides the tree into components of size no less than 1/3n.

1. Pick any vertex x. If it is a good separator label that and recurse.
2. Find all the 3 neighbors of x.
3. Move in the direction of the neighbor which has the largest number of nodes. Repeat Step 2 with the neighbor.

Since finding the separator takes at most $D$ steps, we get a $O(nD\log n)$ algorithm.

**An $O(n\;\log^2 n)$ randomized algorithm**. (moved from comments below)

Pick two vertices x and y randomly. With 1/9 probability they will lie on the opposite sides of a separator. Pick the middle node of the path from $x$ to $y$. See if it is a separator, if not do binary search.

It takes $O(n\;\log n)$ expected time to find the separator. So we get a $O(n\;\log^2 n)$ randomized algorithm.

---

*Background. I learnt about this problem from a friend who works in probabilistic graphical models. The above problem roughly corresponds to learning the structure of a [junction tree](http://en.wikipedia.org/wiki/Tree_decomposition) using an oracle which, given three random variables X,Y and Z, can tell the value of mutual information between X and Y given the value of Z. If the value is close to zero, we may assume that Z lies on the path from X to Y.*

**Tags:** ds.algorithms, reference-request, graph-algorithms, oracles, query-complexity

> **Comments:**
> **username_1**: Please reveal what you already know about the problem, so we don't waste our time reinventing the wheel.  
> **username_0**: @JɛﬀE I've edited my question.  

---

## 2 answers

### Answer by username_1 on 2012-03-19. Score: 5

No.  The following simple adversary strategy implies that any algorithm to reconstruct an $n$-node tree requires at least $\binom{n-1}{2} = n(n-1)/2$ "betweenness" queries.
Arbitrarily label the nodes $0,1,2,\dots,n-1$.  The adversary answers all queries as though the tree is a star with vertex $0$ in the center; think of $0$ as the root and the other nodes as its children.
Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Now suppose the algorithm halts after performing less than $n(n-1)/2$ queries.  Then there must be two vertices $y$ and $z$, neither equal to zero, such that the algorithm has not queried any permutation of the triple $(0,y,z)$.  If the algorithm claims that the tree is not a star with center $0$, the adversary reveals its input, proving the algorithm wrong.  The adversary then reveals that $x$ is actually the only child of $y$, proving the algorithm wrong again.
Update: Oops, just noticed the degree constraint.  Fortunately, this is not a major hurdle.  Replace node $0$ with your favorite binary tree, with the other $n-1$ nodes as leaves in some unknown order, and then reveal this subtree to the reconstruction algorithm.  Reconstructing the resulting $(2n-3)$-node binary tree still requires at least $n(n-1)/2$ queries.  Equivalently, reconstructing an $m$-node binary tree requires at least $(m+3)(m+2)/8$ queries.  (I'm sure a more subtle construction would improve the constant.) As username_0 points out, this generalization doesn't work; queries about internal nodes in the tree impose an ordering on the leaves, which reduced the number of necessary queries.

> **Comments:**
> **username_0**: My question is about constant-degree trees. This argument doesn't work for that case, right?  
> **username_1**: @username_0: Yes, the argument still works; see my update  
> **username_0**: @Jeffe I don't understand the modification. Is the longest diameter among the graphs which the adversary keeps O(log n) then?  
> **username_1**: Yes.  To put it more simply: The adversary has either a complete binary tree with depth $\lg n$, or a complete binary tree with one leaf removed and reinserted as a child of another leaf.  
> **username_0**: @Jeffe You argument seems to imply Omega(n^2) bound for a randomized algorithm too...but there is an O(n log n) randomized algorithm for this case.  
> **username_0**: If the diameter of the tree is D, then I have an algorithm that runs in O(nD log n), so your argument doesn't hold. In the star-graph case, the adversary had n^2 graphs to start with but in the modification that's not the case, right?  
> **username_2**: @username_0: (1) I do not think that this proof of a lower bound works for randomized algorithms.  The adversary can still construct a failing example, but that does not contradict the hypothesis that the randomized algorithm works correctly with high probability.  (2) By the way, it seems that you asked the question knowing the answer.  What did you do that for?  
> **username_1**: @username_0: Oops, you're right; my argument for constant-degree trees is broken.  Queries about triples (a,x,b) where x is in the replacement tree reveal information about the left-to-right ordering of the leaves.  
> **username_1**: @username_0: Do you have a reference for the randomized O(n log n)-time algorithm?  (Is that only for bounded-degree trees?)  
> **username_3**: @JɛﬀE I'm not sure about $O(n \log n)$, but something like $O(n^{\log_2{3}})$ is possible (for bounded degree). Pick each vertex independently with probability 1/2, construct an induced tree recursively, then use its center as "pivot" to split the tree into 2 almost equal parts and construct them recursively (the split can be done in linear time with some technicality, if I am not mistaken). P.S. I mean, that's obviously $o(n^2)$ so the question sounds strange. +1 to JɛﬀE's comment.  
> **username_0**: @JɛﬀE Pick two vertices randomly. With nearly 1/8 probability they will be leaves (since it is a complete binary tree with extra layer of leaves). So the median of the path connecting them will be the root. It takes O(n) expected time to label the root after which we recurse. So we get a O(n log n) randomized algorithm for this case.  
> **username_0**: @Tsuyoshi I meant a randomized algorithm for the case when we know the tree to be an almost complete binary tree (JɛﬀE's construction). Sorry if my earlier comment looked like I knew a O(n log n) randomized algorithm for the actual problem.  
> **username_2**: I see.  Thanks for the explanation, and also thanks for editing the question!  
> **username_0**: @JɛﬀE I think the above randomized algorithm can be modified to work for binary trees: Pick two vertices $x$ and $y$ randomly. With 1/9 probability they will lie on opposite sides of a separator. Pick the middle node of the path from $x$ to $y$. See if it is a good separator, if not do binary search. This takes $O(n \log n)$ expected time to find the separator. So we get a $O(n\;\log^2 n)$ randomized algorithm. Anyway, my question is about the deterministic case, so this probably doesn't say much..  
> **username_1**: If you have a randomized algorithm, then you have an algorithm.  Determinism is overrated.  
> **username_0**: I agree. But I'm unable to find an explicit deterministic algorithm.  
> **username_1**: This problem reminds me of sorting/matching nuts and bolts.  A randomized algorithm that runs in $O(n \log n)$ time with high probability is easy — it's just [randomized quicksort](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/05-nutsbolts.pdf).  There is a deterministic $O(n\log n)$-time algorithm, but it is [seriously nontrivial](http://dl.acm.org/citation.cfm?id=296075).  
> **username_0**: The previous work mentioned in that paper looks more readable. In Alon et.al's paper (which achieves $O(n\;\log^4 n)$-time) this sentence caught my eye: "The algorithm constructs `deterministic samples' by applying expander graphs in an interesting way." Finding the median nut is definitely harder than finding the median of $n$ numbers. So I'm wondering if there is a paper that explains how to find the median of $n$ numbers in  $o(n\;\log n)$ time using expander graphs.  

---

### Answer by username_0 on 2013-10-15. Score: 5

Anindya Sen and I have a [paper](http://link.springer.com/chapter/10.1007%2F978-3-642-40935-6_14) in ALT '13 where we give an $\tilde O(n \sqrt{n})$ algorithm for this problem. We don't know if a better algorithm is possible.


---

