Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.

For example, consider the following two trees:


Example trees T and U are isomorphic.
An isomorphism (bijection) is described in the table below:

  T          U
  1          2
  2          4
  3          1
  4          5
  5          3
  "white"    "green"
  "blue"     "white"     

Below are some things to know about the problem:

  • Nodes are colored
  • edges are not colored.
  • Nodes are free to be any color. Adjacent nodes are allowed to be the same color.
  • which node is the root node of each tree cannot be changed.
  • children are un-ordered.
  • the tree is not necessarily a binary tree. a node could have 3 children, 4 children, 5, etc...

Formally, a colored tree is a tuple (VS, ES, root, color_set, color_map) such that:

  • VS is the vertex set
  • ES is the edge set
  • (VS, ES) is a undirected tree
  • root is a element of VS
  • color_set is a set of objects called "colors"
  • color_map is a mapping from VS to color_set
  • every element of color_set appears in the range of color_map at least once. That is, every color is applied to at least one node.

colored trees T and U are isomorphic if and only if there exists a bijection, PHI from the vertex set of T, VT, to the vertex set of U, VU such that:

  • the root of one tree is matched to the root of the other tree
  • for all nodes v, w in VT, {v, w} is an edge in tree T if and only if {PHI(v), PHI(w)} is an edge in tree U
  • for all nodes v, w in VT, v and w are the same color in tree T if and only if PHI(v), PHI(w) are the same color in tree U
  • 1
    $\begingroup$ Do you know how to solve this without the colors? That would be a good start. $\endgroup$ – Yuval Filmus Jun 15 '19 at 14:24

Let f be a function from the color set of the first tree to the color set of the second tree. The function f is initially defined only partially, for e.g. that f(color(root of first tree)) = color(root of second tree).

At each node of the tree, isomorphism is checked by trying both ways of mapping its children and checking whether the sub tree rooted at the left child of first tree is isomorphic to the left or the right subtree of the node in the second tree. This can be checked by recursive function calls, which can pass the current root node of the two trees and existing f as arguments in the recursive function calls.

It appears that this algorithm perhaps even runs in linear time. As the recursion gets deeper, f would be more fully defined and number of recursive function calls might reduce. The function modifying f must keep it consistent with the previous f which it received as parameter.

  • $\begingroup$ The tree is not necessarily binary. $\endgroup$ – Yuval Filmus Jun 22 '19 at 15:23
  • $\begingroup$ Oh well, that makes it more difficult and interesting. $\endgroup$ – mo2019 Jun 22 '19 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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