Rooted tree isomorphism problem

This article describes a decision problem from or related to graph theory. The problem is mentioned in this wiki due to its close relation with computational and decision problems in computational group theory

Description

Given data

We are given two rooted trees $(T_{1},v_{1})$ and $(T_{2},v_{2})$, both described by means of their adjacency matrices.

Goal

We need to find whether there is a rooted tree isomorphism between $T_{1}$ and $T_{2}$, viz an isomorphism that maps $v_{1}$ to $v_{2}$.

Solution

Notion of orientation

Initially, the following might appear a tempting way to solve the rooted tree isomorphism problem: start at the root of both trees, and then at each stage, check for each of the subtrees whether they are isomorphic. The problem withthis approach is that since there is no natural orientation to the tree, it is not clear which subtree of $T_{1}$ should be compared with which subtree of $T_{2}$.

A way to circumvent this problem is to provide a canonical orientation to the tree, viz an orientation that depends only on the isomorphism class of the tree. In other words, the game-plan is that we provide orientations to both trees in such a way that the two trees are isomorphic as rooted trees if and only if they are isomorphic as rooted oriented trees with those orientations.

The idea behind the canonical orientation is roughly as follows: if the two subtrees coming under the two children are isomorphic, then the orientation does not matter. Otherwise, we give the smaller subtree an earlier position in the orientation.

Broad outline

The way to solve the rooted tree isomorphism problem is by means of an algorithm that roughly moves upwards from the leaves to the root.

1. Perform a depth-first search of the graph and hence, for each vertex, store the depth of that vertex, who its parents are, and who its children are. In particular, make a list of the leaves.
2. Now,
3. At each step, having coloured the leaf vertices, go one step up and colour all the vertices by the ordered tuple of the colours of all ist children. Of course, these ordered tuples may be huge in size, so simply reorder the coloured things lexicographically and colour by the index in the sorted ordering.
4. Keep doing this till you obtain a colouring on all the vertices
5. having done this colouring, simply obtain the associated colouring

Analysis of running time

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.