AHU Algorithm

AHU algorithm for determining whether two rooted trees are isomorphic.

Besides testing tree isomorphism, another common approach is tree hashing.

Prerequisites: tree basics, tree centroid.

The examples in the references are recommended for further reading.

Definition of Tree Isomorphism

Rooted Tree Isomorphism

For two rooted trees $T_1(V_1,E_1,r_1)$ and $T_2(V_2,E_2,r_2)$, if there exists a bijection $\varphi: V_1 \rightarrow V_2$ such that

and also $\varphi(r_1)=r_2$, then the rooted trees $T_1(V_1,E_1,r_1)$ and $T_2(V_2,E_2,r_2)$ are called isomorphic.

Unrooted Tree Isomorphism

For two unrooted trees $T_1(V_1,E_1)$ and $T_2(V_2,E_2)$, if there exists a bijection $\varphi: V_1 \rightarrow V_2$ such that

then the unrooted trees $T_1(V_1,E_1)$ and $T_2(V_2,E_2)$ are called isomorphic.

In simple terms, if the vertices of tree $T_1$ can be relabeled so that $T_1$ and $T_2$ become exactly the same, the two trees are isomorphic.

Reducing the Problem

The unrooted tree-isomorphism problem can be reduced to the rooted tree-isomorphism problem as follows.

For unrooted trees $T_1(V_1, E_1)$ and $T_2(V_2,E_2)$, first find all their centroids separately.

• If the two unrooted trees have different numbers of centroids, they are not isomorphic.
• If both have exactly $1$ centroid, call them $c_1$ and $c_2$. If the rooted trees $T_1(V_1,E_1,c_1)$ and $T_2(V_2,E_2,c_2)$ are isomorphic, then the unrooted trees $T_1(V_1, E_1)$ and $T_2(V_2,E_2)$ are isomorphic; otherwise they are not.
• If both have exactly $2$ centroids, call them $c_1,c'_1$ and $c_2,c'_2$. If either the rooted trees $T_1(V_1,E_1,c_1)$ and $T_2(V_2,E_2,c_2)$ are isomorphic or the rooted trees $T_1(V_1,E_1,c'_1)$ and $T_2(V_2,E_2,c_2)$ are isomorphic, then the unrooted trees $T_1(V_1, E_1)$ and $T_2(V_2,E_2)$ are isomorphic; otherwise they are not.

Thus, once rooted tree isomorphism is solved, unrooted tree isomorphism can be reduced to it by the method above.

Suppose an algorithm solves rooted tree isomorphism in $O(\left|V\right|)$ time. Then the method above also solves unrooted tree isomorphism in $O(\left|V\right|)$ time.

Naive AHU Algorithm

The naive AHU algorithm is based on balanced-parenthesis sequences.

Principle 1

Every valid parenthesis sequence corresponds uniquely to a rooted tree, and the parenthesis sequence of a tree is formed by concatenating the parenthesis sequences of its subtrees. If we change the order in which the subtree sequences are concatenated to obtain a new parenthesis sequence, the tree represented by the new sequence is isomorphic to the tree represented by the original sequence.

Principle 2

Tree isomorphism is transitive. That is, if $T_1$ and $T_2$ are isomorphic and $T_2$ and $T_3$ are isomorphic, then $T_1$ and $T_3$ are isomorphic.

Corollary

Consider the recursive algorithm for constructing a tree's parenthesis sequence. When backtracking, concatenate the sequences of the subtrees. If the lexicographically smaller sequence is always concatenated first, denote the final result by $NAME$.

The subtree rooted at vertex $r$ has $NAME$; vertex $r$ has $NAME$, denoted $NAME(r)$. Then, for rooted trees $T_1(V_1,E_1,r_1)$ and $T_2(V_2,E_2,r_2)$, if $NAME(r_1)=NAME(r_2)$, the trees $T_1$ and $T_2$ are isomorphic.

Naming Algorithm

AHU Algorithm

Complexity Analysis

For a rooted tree with $n$ vertices, suppose it is a path. Then the longest vertex name can have length $n$, so the complexity of ASSIGN-NAME is a constant multiple of $1+2+\cdots+n$, namely $\Theta(n^2)$. Therefore, the naive AHU algorithm has complexity $O(n^2)$.

Optimized AHU Algorithm

The drawback of the naive AHU algorithm is that a tree's $NAME$ may become too long, so we optimize this aspect.

Principle 1

Partition the tree into levels. The shortest distance from a vertex on level $i$ to the root is $i$. On level $i$, a vertex's $NAME$ can be formed only by concatenating, from vertices on level $i+1$, their $NAME$.

Principle 2

Within the same level, a vertex's $NAME$ can be uniquely identified by its rank within that level.

Note that this ranking is defined jointly for the two trees. If vertex $u$ is on level $i$, the rank of vertex $u$ equals the number of vertices in $T_1$ and $T_2$ on level $i$ whose $NAME$ is smaller than $NAME(u)$.

Corollary

Replace each vertex's original $NAME$ by its rank within its level, and replace the original concatenation of vertex $NAME$s by adding elements to an array.

Using integers and arrays instead of strings preserves correctness while greatly reducing the complexity.

Complexity Analysis

First note that on level $i$, the concatenated $NAME$ values have total length equal to the sum of the degrees of vertices on level $i$, namely the total number of vertices on level $i+1$; denote this by $L_i$. The next step treats these $NAME$ values as strings (arrays) and sorts them, then replaces them by their ranks within the level. The following facts give the complexity of sorting strings with total length $L$, where there are $m$ strings:

1. We can use radix sort to sort them in $O(L+|\Sigma|)$ time, where $|\Sigma|$ is the size of the character set. (Some implementation details are given in the references.)
2. We can use quicksort to sort them in $O(L \log m)$ time. The rough proof is that the height of the quicksort recursion tree is $O(\log m)$, and the complexity of comparing two strings of lengths $\ell_1$ and $\ell_2$ by brute force is $O(\min\{\ell_1,\ell_2\})$.

In the AHU algorithm, the character set size of the strings on level $i$ is at most the number of vertices on level $i+1$, namely $L_i$, so radix sorting is linear. Since $\sum_i L_i=O(n)$, adding the complexities of all levels shows that the total complexity is $T(n)=O(n)$ when radix sorting is used. Similarly, if quicksort is used to sort the strings, then $T(n)=O(n \log n)$.

Example

SPOJ-TREEISO

Problem statement: Given two unrooted trees, determine whether they are isomorphic.

// Tree Isomorphism, O(nlogn)
// replace quick sort with radix sort ==> O(n)
// Author: _Backl1ght
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
constexpr int N = 1e5 + 5;
constexpr int MAXN = N << 1;

int n;

struct Edge {
  int v, nxt;
} e[MAXN << 1];

int head[MAXN], sz[MAXN], f[MAXN], maxv[MAXN], tag[MAXN], tot, Max;
vector<int> center[2], L[MAXN], subtree_tags[MAXN];

void addedge(int u, int v) {  // Build graph
  e[tot].v = v;
  e[tot].nxt = head[u];
  head[u] = tot++;
  e[tot].v = u;
  e[tot].nxt = head[v];
  head[v] = tot++;
}

void dfs_size(int u, int fa) {  // Find the size
  sz[u] = 1;
  maxv[u] = 0;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs_size(v, u);
    sz[u] += sz[v];
    maxv[u] = max(maxv[u], sz[v]);
  }
}

void dfs_center(int rt, int u, int fa, int id) {
  maxv[u] = max(maxv[u], sz[rt] - sz[u]);
  if (Max > maxv[u]) {
    center[id].clear();
    Max = maxv[u];
  }
  if (Max == maxv[u]) center[id].push_back(u);  // Push back if equal
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa) continue;
    dfs_center(rt, v, u, id);
  }
}

int dfs_height(int u, int fa, int depth) {  // Recursively find the height
  L[depth].push_back(u);
  f[u] = fa;
  int h = 0;
  for (int i = head[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    if (v == fa) continue;
    h = max(h, dfs_height(v, u, depth + 1));
  }
  return h + 1;
}

void init(int n) {  // Initial processing
  for (int i = 1; i <= 2 * n; i++) head[i] = 0;
  tot = 1;
  center[0].clear();
  center[1].clear();

  int u, v;
  for (int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    addedge(u, v);
  }
  dfs_size(1, -1);
  Max = n;
  dfs_center(1, 1, -1, 0);

  for (int i = 1; i <= n - 1; i++) {
    cin >> u >> v;
    addedge(u + n, v + n);
  }
  dfs_size(1 + n, -1);
  Max = n;
  dfs_center(1 + n, 1 + n, -1, 1);
}

bool cmp(int u, int v) { return subtree_tags[u] < subtree_tags[v]; }

bool rootedTreeIsomorphism(int rt1, int rt2) {
  for (int i = 0; i <= 2 * n + 1; i++) L[i].clear(), subtree_tags[i].clear();
  int h1 = dfs_height(rt1, -1, 0);
  int h2 = dfs_height(rt2, -1, 0);
  if (h1 != h2) return false;
  int h = h1 - 1;
  for (int j = 0; j < (int)L[h].size(); j++) tag[L[h][j]] = 0;
  for (int i = h - 1; i >= 0; i--) {
    for (int j = 0; j < (int)L[i + 1].size(); j++) {
      int v = L[i + 1][j];
      subtree_tags[f[v]].push_back(tag[v]);
    }

    sort(L[i].begin(), L[i].end(), cmp);

    for (int j = 0, cnt = 0; j < (int)L[i].size(); j++) {
      if (j && subtree_tags[L[i][j]] != subtree_tags[L[i][j - 1]]) ++cnt;
      tag[L[i][j]] = cnt;
    }
  }
  return subtree_tags[rt1] == subtree_tags[rt2];
}

bool treeIsomorphism() {
  if (center[0].size() == center[1].size()) {
    if (rootedTreeIsomorphism(center[0][0], center[1][0])) return true;
    if (center[0].size() > 1)
      return rootedTreeIsomorphism(center[0][0], center[1][1]);
  }
  return false;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  while (T--) {
    cin >> n;
    init(n);
    cout << (treeIsomorphism() ? "YES" : "NO") << '\n';
  }
  return 0;
}

References

Most of this article is translated from Paper and Slide. The proofs in the references are more complete and rigorous; this article simplifies them somewhat.

For a complexity analysis of the AHU algorithm and the linear-time radix sort for strings, see Section 3.2, Radix sorting, of The Design and Analysis of Computer Algorithms, especially Example 3.2.