Example NP problems published in A. Lucas, Front. Phys. (2014) - Graph isomorphism problem¶

This example code implements the graph isomorphism problem introduced in the paper A. Lucas, "Ising formulations of many NP problems", Front. Phys. (2014) using Fixstars Amplify. Other NP-complete and NP-hard problems introduced in the same paper are also discussed below (the corresponding sections in the paper are shown in the brackets).

• Graph partitioning problem (Sec. 2.2).
• Maximum clique problem (Sec. 2.3)
• Exact cover problem (Sec. 4.1)
• Set packing problem (Sec. 4.2)
• Minimum vertex cover problem (Sec. 4.3)
• Satisfiability problem (SAT) (Sec. 4.4)
• Minimum maximum matching problem (Sec. 4.5)
• Graph coloring problem (Sec. 6.1)
• Clique cover problem (Sec. 6.2)
• Job sequencing problem with integer lengths (Sec. 6.3)
• Hamiltonian cycle problem (Sec. 7.1)
• Directed feedback vertex set problem (Sec. 8.3)
• Minimum feedback edge set problem (Sec. 8.5)
• Graph isomorphism problem (Sec. 9)

Graph isomorphism problem¶

Two (simple) graphs are isomorphic if there is a one-to-one correspondence (isomorphic mapping) between their vertices, and if an edge connects two vertices in one graph, then the two corresponding vertices in the other graph are also connected by an edge. In another way, two graphs are isomorphic if they form the same picture when drawn with their vertices appropriately aligned.

In general, when the size of a graph is large, it is difficult to determine in practical time whether two graphs are isomorphic. In this section, we will create a program to search for isomorphic maps using Fixstars Amplify. The formulation of this sample program follows that of Sec. 9 of A. Lucas, Front. Phys. (2014).

Problem definition¶

First, we create example graphs $G_1$ and $G_2$ using NetworkX. At this time, $G_1$ and $G_2$ should be isomorphic.

These two graphs are isomorphic maps if they correspond, for example, as shown in the following figure. If a vertex of color A is connected to a vertex of color B by an edge in one graph, then a vertex of color A is connected to a vertex of color B by an edge in the other graph (ignore the numbers on each vertex here for now).

Formulation.¶

If $G_1$ and $G_2$ have different numbers of vertices, they are not isomorphic, so below, we consider only the case where $G_1$ and $G_2$ have the same number of vertices. Let $N$ be the number of vertices in $G_1$. Formulate as follows.

Decision variables¶

To represent the correspondence between two graphs, we prepare a binary variable table $q$ of $N\times N$. When the $i$-th vertex of $G_1$ corresponds to the $j$-th vertex of $G_2$, the $i$ row $j$ column of $q$ should be $1$.

For example, comparing the correspondence between the number and color of the vertices connected by edges in $G_1$ and $G_2$ in the figure above, the two graphs corresponded as follows.

Vertices of G1	Vertices of G2	Color
0	0	Blue
1	2	Orange
2	4	Green
3	1	Red
4	3	Purple

Representing this in a table of binary variables $q$, we have the following.

G1 \ G2	0	1	2	3	4
0	1	0	0	0	0
1	0	0	1	0	0
2	0	0	0	0	1
3	0	1	0	0	0
4	0	0	0	1	0

Objective function¶

Since the graph isomorphism problem is to find one that satisfies the conditions, we do not need to consider the objective function.

Constraints¶

For $q$ to represent an isomorphic map, we need the following.

• Condition 1: Each vertex of $G_1$ corresponds to one vertex of $G_2$. That is, each row of $q$ has only one $1$.

• Condition 2: Each vertex of $G_2$ corresponds to one vertex of $G_1$. That is, each column of $q$ has only one $1$.

• Condition 3: If vertices $u$ and $v$ in $G_1$ are connected by an edge, then the $2$ vertices in $G_2$ corresponding to $u$ and $v$ are also connected by an edge.

• Condition 4: If vertices $s$ and $t$ in $G_2$ are connected by an edge, then the $2$ vertices of $G_1$ corresponding to $s$ and $t$ are also connected by an edge.

The conditions 1 and 2 are

$$\begin{align*} \sum_{j = 0}^{N-1} q_{i, j} = 1 \quad & \text{for} \quad i \in \{0, 1, \ldots, N-1\} \\ \sum_{i = 0}^{N-1} q_{i, j} = 1 \quad & \text{for} \quad j \in \{0, 1, \ldots, N-1\}. \end{align*}$$

Condition 3 can be reworded as "if the vertices $u$ and $v$ of $G_1$ are connected by an edge and the vertices $s$ and $t$ of $G_2$ are not connected by an edge, $u$ and $s$ and $v$ and $t$ must not correspond to each other". Thus, this condition can be

$$q_{u, s} q_{v, t} = 0 \quad \text{for} \quad (u\rightarrow v) \in E_1, (s\rightarrow t) \notin E_2.$$

Here, $E_1$ and $E_2$ are the edge sets of $G_1$ and $G_2$, respectively.

Similarly, the condition 4 is

$$q_{u, s} q_{v, t} = 0 \quad \text{for} \quad (u\rightarrow v) \notin E_1, (s\rightarrow t) \in E_2.$$

If the conditions 1-4 hold, then graphs $G_1$ and $G_2$ are isomorphic. The above completes the formulation of the graph isomorphism problem.

Implementation¶

Using the problem and formulation described above, let us implement and solve the problem. First, we create binary decision variables $q$ with VariableGenerator.

Next, we create the constraints corresponding to the conditions 1 and 2. Since these are conditions that there is only one $1$ in each row and column of $q$, we can construct them using one_hot.

We create the corresponding constraints for conditions 3 and 4. The condition 3 is the constraint $q_{u, s} q_{v, t} = 0 \bigl((u\rightarrow v) \in E_1, (s\rightarrow t) \notin E_2 \bigr)$ and the condition 4 is the replacement of $G_1$ and $G_2$ in the condition 3.

The created constraints are converted into an optimization model.

Configure the client and execute the solver on the Amplify Annealing Engine (AE).

Let us check whether we found the isomorphic mapping. Since Amplify SDK automatically filters the solutions that satisfy the constraints, if the result is not empty, you know that a solution has been found that satisfies the constraints.

Lastly, the corresponding vertices of two graphs that are isomorphic maps are displayed in the same color.