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 NPcomplete and NPhard 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 onetoone 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.
import networkx as nx
N = 5 # Number of vertices
G1 = nx.Graph()
G1.add_nodes_from(range(N))
edge_list1 = [(0, 1), (0, 4), (1, 2), (2, 3), (3, 4)]
G1.add_edges_from(edge_list1)
pos1 = nx.circular_layout(G1)
nx.draw_networkx(G1, node_size=600, font_color="w", pos=pos1)
G2 = nx.Graph()
G2.add_nodes_from(range(N))
edge_list2 = [(0, 2), (0, 3), (1, 3), (1, 4), (2, 4)]
G2.add_edges_from(edge_list2)
pos2 = nx.circular_layout(G2)
nx.draw_networkx(G2, node_size=600, font_color="w", pos=pos2)
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}^{N1} q_{i, j} = 1 \quad & \text{for} \quad i \in \{0, 1, \ldots, N1\} \\ \sum_{i = 0}^{N1} q_{i, j} = 1 \quad & \text{for} \quad j \in \{0, 1, \ldots, N1\}. \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 14 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
.
from amplify import VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, N))
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
.
from amplify import one_hot
constraint1 = one_hot(q, axis=1)
constraint2 = one_hot(q, axis=0)
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.
from amplify import equal_to, sum as amplify_sum
constraint3 = amplify_sum(
equal_to(q[u, s] * q[v, t], 0) + equal_to(q[u, v] * q[v, s], 0)
for (u, v) in G1.edges
for (s, t) in nx.non_edges(G2)
)
constraint4 = amplify_sum(
equal_to(q[u, s] * q[v, t], 0) + equal_to(q[u, v] * q[v, s], 0)
for (u, v) in nx.non_edges(G1)
for (s, t) in G2.edges
)
The created constraints are converted into an optimization model.
model = constraint1 + constraint2 + constraint3 + constraint4
Configure the client and execute the solver on the Amplify Annealing Engine (AE).
from amplify import FixstarsClient, solve
from datetime import timedelta
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you use Amplify in a local environment or Google Colaboratory, enter your Amplify API token.
client.parameters.timeout = timedelta(milliseconds=1000) # timeout is 1000 ms
# Solve the problem
result = solve(model, client)
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.
if len(result) == 0:
print("No isomorphic mapping has been found.")
else:
print("The isomorphic mapping has been found.")
Lastly, the corresponding vertices of two graphs that are isomorphic maps are displayed in the same color.
import matplotlib.pyplot as plt
import numpy as np
values = q.evaluate(result.best.values)
# Vertex "i" in G1 corresponds to vertex "vertex_map[i]" in G2
vertex_map = np.where(values == 1)[1]
colors = np.array([f"C{i}" for i in range(N)])
# Let the ith vertex of G2 be painted with the ith color
colors2 = colors
# Paint the ith vertex of G1 with the same color as the "vertex_map[i]"th vertex of G2
colors1 = colors[vertex_map]
# Visualize
fig, ax = plt.subplots(nrows=1, ncols=2, figsize=(12, 4))
nx.draw_networkx(
G1, node_size=600, node_color=colors1, font_color="w", pos=pos1, ax=ax[0]
)
nx.draw_networkx(
G2, node_size=600, node_color=colors2, font_color="w", pos=pos2, ax=ax[1]
)