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 trees $T_{1}$ and $T_{2}$, both described by means of their adjacency matrices.

Goal

We need to find whether there is a tree isomorphism between $T_{1}$ and $T_{2}$.

Relation with other problems

Problems that are solved using it

• Bounded degree graph isomorphism: This is the graph isomorphism problem where the degrees of all vertices are bounded. Bounded degree graph isomorphism requires us to solve a tree isomorphism problem for bounded degree trees.

Problems it reduces to

The tree isomorphism problem can be solved by making repeated calls to the rooted tree isomorphism problem as discussed below.

Solution

Idea

We know that a tree can be viewed as a rooted tree about any vertex. Thus, the idea is:

• Fix one vertex $v_{1}$ in $T_{1}$
• Cycle over all possibilities for the vertex $v_{2}$ in $T_{2}$, and for each, use the rooted tree isomorphism problem to check whether $(T_{1},v_{1})$ is isomorphic to $(T_{2},v_{2})$.