2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 center 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." $\endgroup$
    – D.W.
    Aug 25, 2016 at 23:32
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Aug 26, 2016 at 0:02

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – R B
    Mar 28, 2016 at 16:57
  • $\begingroup$ If you need an oracle for subtree isomorphism it is a polynomial time thing, not something NP hard. $\endgroup$
    – Chad Brewbaker
    Mar 28, 2016 at 17:05
  • $\begingroup$ 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. $\endgroup$
    – R B
    Mar 28, 2016 at 17:08
  • $\begingroup$ I am curious what sort of trees would be minimal. I have no intuition as to what type of small subtrees would be produced. $\endgroup$
    – Chad Brewbaker
    Mar 28, 2016 at 18:42
1
$\begingroup$

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 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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Tim
    Aug 25, 2016 at 23:59
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W.
    Aug 26, 2016 at 0:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.