Bounded-degree graph 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

The problem $BDGI_{d}$ where $d$ is a fixed constant, is defined as follows:

Two graphs $X_{1}=(V_{1},E_{1})$ and $X_{2}=(V_{2},E_{2})$ specified in some standard format (such as incidence matrix, adjacency matrix etc.)

By graph here we mean finite simple undirected graph, though, by suitable equivalences and reductions, we can consider directed graphs and allow loops and parallel edges.

Further, we are given the promise (that can be readily verified) that the degree of every vertex in both $X_{1}$ and $X_{2}$ is bounded above by $d$.

Goal

We need to determine whether $X_{1}$ and $X_{2}$ are isomorphic as abstract finite simple undirected graphs.

Solution

It turns out that the problem can be solved in polynomial-time. The proof for this is fairly complicated, and the result is termed Luks' theorem.

Initial simplification

Since the property of having degree boudend by $d$ is preserved by all subgraphs, one can in particular use the connected components technique to reduce the problem to bounded degree graph isomorphism for connected graphs.