<p>Your problem is in $P$.  In fact, it can be solved in $O(n^2)$ time.</p>

<p>Given a tree, you can find a label (a binary string) that is a <a href="https://en.wikipedia.org/wiki/Graph_canonization" rel="nofollow">canonical form</a> for the tree (i.e., all isomorphic trees will share the same label).  The algorithm also computes a label for each of its subtrees along the way.  The algorithm uses $O(n)$ space and $O(n^2)$ time.  Compute these labels for $T_1$ and $T_2$ and all of their subtrees.  Store the labels of all subtrees of $T_2$ in a hashtable.</p>

<p>There are only $O(n)$ candidates for $T$: since we want $T$ to be isomorphic to some subtree of $T_1$, each subtree of $T_1$ is a candidate for $T$.  Given a candidate for $T$, you can test whether it is an acceptable solution in $O(n)$ time: check whether its label matches any of the labels of the subtrees of $T_2$.  Out of all the acceptable candidates, keep the smallest one.  The total running time to check all candidates is $O(n^2)$ time.</p>

<p>Thus, we obtain an algorithm that solves your problem in $O(n^2)$ time.</p>

CC BY-SA 3.0
2016-08-25T23:59:07.327Z
Note that this assumes rooted trees, in which a subtree is defined to contain all elements reachable from a given node by moving only away from the root. In my interpretation of the original question, subtrees are defined as subgraphs which are trees.
Tim
CC BY-SA 3.0
2016-08-26T00:01:24.363Z
@Tim, good point.  But, it'd probably be more useful to raise this comment on the question, than on a particular answer.  If there is a potential for ambiguity, the burden is on the person asking the question to define their terms clearly.
D.W.
CC BY-SA 3.0
2016-08-25T23:30:59.733Z
2016-08-25T23:30:59.733Z
D.W.
<p>You can put a tree into a cannonical form in $O(n)$ with leaf contractions. Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New York, pp. 153–182</p>

<p>When $T_{1}$ and $T_{2}$ are isomorphic you can solve it in $O(n)$.</p>

<p>Shamir's paper has $O({k^{1.5}\over log\ k}n)$ for testing if one tree is a subtree of the other, <a href="https://www.cs.bgu.ac.il/~dekelts/publications/subtree.pdf" rel="nofollow">https://www.cs.bgu.ac.il/~dekelts/publications/subtree.pdf</a> </p>

<p>Not sure if that helps.</p>

CC BY-SA 3.0
2016-03-28T16:57:22.587Z
Thanks Chad. I might be missing something, but how do you use Shamir's results to solve this problem? We can start by verifying that $T_1$ has no isomorphic sub-tree in $T_2$, but how do we then find the minimal tree that also satisfy this?
R B
CC BY-SA 3.0
2016-03-28T17:05:14.730Z
If you need an oracle for subtree isomorphism it is a polynomial time thing, not something NP hard.
Chad Brewbaker
CC BY-SA 3.0
2016-03-28T17:08:47.733Z
Yes, I'm familiar with this result, thanks. Specifically, we are looking into the problem of finding a subtree which is frequent in a graph family $\mathcal T_1$ (e.g., appears in more than half of its trees) but **not** frequent in $\mathcal T_2$. Before addressing the general problem, I wanted to ask if anything is known about the simpler case of only one tree in each family. Thanks again.
R B
CC BY-SA 3.0
2016-03-28T18:42:23.917Z
I am curious what sort of trees would be minimal. I have no intuition as to what type of small subtrees would be produced.
Chad Brewbaker
CC BY-SA 3.0
2016-03-28T16:02:06.150Z
2016-03-28T16:02:06.150Z
Chad Brewbaker
<p>Consider the problem that receives two trees $T_1$, $T_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T_1$ which is isomorphic to $T$, but there is no such isomorphic subtree in $T_2$.</p>

<blockquote>
  <p>What is known about the complexity of this problem?</p>
</blockquote>

CC BY-SA 3.0
2016-08-25T23:32:03.083Z
What do you already know about this problem?  What's the best algorithm you know?  Do you know of any non-trivial lower bound?  As our [help/on-topic] says, "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [...] Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing, not on shirking."
D.W.
CC BY-SA 3.0
2016-08-26T00:02:02.650Z
Can you define what you mean by "subtree"?  Are you talking about rooted trees, and a subtree is the set of all descendants of some node of the tree?  Or unrooted trees with a different notion of subtree?  This will make a significant difference to the answer.
D.W.
<cc.complexity-theory><ds.algorithms><graph-algorithms><tree>
Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$
R B
# Finding a minimum tree which is isomorphic to a subtree of $T_1$ but not to a subtree of $T_2$

(Asked by: username_0 on 2016-03-27)

Consider the problem that receives two trees $T\_1$, $T\_2$, and asks to find a minimum size tree $T$ such that there exists a subtree of $T\_1$ which is isomorphic to $T$, but there is no such isomorphic subtree in $T\_2$.

> What is known about the complexity of this problem?

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, tree
> **Comments:**
> **username_1**: What do you already know about this problem?  What's the best algorithm you know?  Do you know of any non-trivial lower bound?  As our [help/on-topic] says, "You should only post questions you're actually seriously thinking about. Users are expected to do their part and try to answer their question by themselves before posting them on cstheory and asking for help from others. [...] Try to make your question interesting for others by providing some background knowledge. Remember, questions should be based on knowledge sharing, not on shirking."  
> **username_1**: Can you define what you mean by "subtree"?  Are you talking about rooted trees, and a subtree is the set of all descendants of some node of the tree?  Or unrooted trees with a different notion of subtree?  This will make a significant difference to the answer.  

---

## 2 answers

### Answer by username_1 on 2016-08-25. Score: 1

Your problem is in $P$. In fact, it can be solved in $O(n^2)$ time.

Given a tree, you can find a label (a binary string) that is a [canonical form](https://en.wikipedia.org/wiki/Graph_canonization) for the tree (i.e., all isomorphic trees will share the same label). The algorithm also computes a label for each of its subtrees along the way. The algorithm uses $O(n)$ space and $O(n^2)$ time. Compute these labels for $T\_1$ and $T\_2$ and all of their subtrees. Store the labels of all subtrees of $T\_2$ in a hashtable.

There are only $O(n)$ candidates for $T$: since we want $T$ to be isomorphic to some subtree of $T\_1$, each subtree of $T\_1$ is a candidate for $T$. Given a candidate for $T$, you can test whether it is an acceptable solution in $O(n)$ time: check whether its label matches any of the labels of the subtrees of $T\_2$. Out of all the acceptable candidates, keep the smallest one. The total running time to check all candidates is $O(n^2)$ time.

Thus, we obtain an algorithm that solves your problem in $O(n^2)$ time.

> **Comments:**
> **username_2**: Note that this assumes rooted trees, in which a subtree is defined to contain all elements reachable from a given node by moving only away from the root. In my interpretation of the original question, subtrees are defined as subgraphs which are trees.  
> **username_1**: @Tim, good point.  But, it'd probably be more useful to raise this comment on the question, than on a particular answer.  If there is a potential for ambiguity, the burden is on the person asking the question to define their terms clearly.  

---

### Answer by username_3 on 2016-03-28. Score: 1

You can put a tree into a cannonical form in $O(n)$ with leaf contractions. Read, Ronald C. (1972), "The coding of various kinds of unlabeled trees", Graph Theory and Computing, Academic Press, New York, pp. 153–182

When $T\_{1}$ and $T\_{2}$ are isomorphic you can solve it in $O(n)$.

Shamir's paper has $O({k^{1.5}\over log\ k}n)$ for testing if one tree is a subtree of the other, <https://www.cs.bgu.ac.il/~dekelts/publications/subtree.pdf>

Not sure if that helps.

> **Comments:**
> **username_0**: Thanks Chad. I might be missing something, but how do you use Shamir's results to solve this problem? We can start by verifying that $T_1$ has no isomorphic sub-tree in $T_2$, but how do we then find the minimal tree that also satisfy this?  
> **username_3**: If you need an oracle for subtree isomorphism it is a polynomial time thing, not something NP hard.  
> **username_0**: Yes, I'm familiar with this result, thanks. Specifically, we are looking into the problem of finding a subtree which is frequent in a graph family $\mathcal T_1$ (e.g., appears in more than half of its trees) but **not** frequent in $\mathcal T_2$. Before addressing the general problem, I wanted to ask if anything is known about the simpler case of only one tree in each family. Thanks again.  
> **username_3**: I am curious what sort of trees would be minimal. I have no intuition as to what type of small subtrees would be produced.  

---

