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

Why should we even expect that there is such a polynomial-time algorithm? The comment

Do you know how to solve this without the colors? That would be a good start. – Yuval Filmus Jun 15 '19 at 14:24

has an upvote, but it only hints implicitly that there is a (simple?) solution. Let me try to guess the (simple?) solution that is expected here. The AHU algorithm by Aho, Hopcroft and Ullman produces a canonical labeling of trees. Let's interpret the AHU algorithm as an efficient implementation of color refinement for rooted trees, and ask whether color refinement for "labeled trees" (isomorphism of "colored trees" would not allow to swap colors) would always be able to decide isomorphism. The answer is "no", because isomorphism of labeled trees is GI complete:

From a graph G, construct a rooted labeled tree T by putting a node below the root of the tree for every vertex of G. For every edge of G, put two nodes with the same label on the next lower level. An edge has two endpoints, connect the corresponding vertices (or rather the tree nodes corresponding to them) each with one of the tree nodes corresponding to the edge. constructing a labeled tree from a graph that allows to decide isomorphism

The link above also makes it clear that this is well known by citing

Theorem: Marked tree isomorphism is isomorphism complete

from section 6.4 Marked Graphs and Marked Trees in Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo. They used the definition that “A marked graph is a graph together with a partition of its vertices. An isomorphism of marked graphs is an isomorphism of the underlying graphs which preserves the partitioning.”

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\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.