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

This example code implements the graph coloring 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)
Minimal maximal 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 coloring problem¶

For a graph $G$ and a natural number $K$, the problem of determining whether the vertices of $G$ can be painted with $K$ colors so that two vertices connected by an edge do not have the same color is called the graph coloring problem.

For example, in the following diagram, the vertices of $G$ are painted with either blue, orange, or gray, and for any edge, the two endpoints are different colors.

In this example program, we will solve the graph coloring problem using Fixstars Amplify. The formulation follows the one in Sec. 6.1 of A. Lucas, Front. Phys. (2014).

Problem definition¶

First, as an example, we will create a graph $G$ using NetworkX. Also, let $K$, the number of colors, be $3$.

In [ ]:

import networkx as nx
    
K = 3  # Number of colors
N = 6  # Number of vertices of the graph
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [(0, 1), (0, 2), (0, 4), (0, 5), (1, 2), (1, 5), (2, 3), (3, 4), (4, 5)]
G.add_edges_from(edge_list)
    
pos = nx.circular_layout(G)
    
nx.draw_networkx(G, node_size=600, font_color="w", pos=pos)

Formulation¶

Below, let $N$ be the number of vertices in the graph $G$. Also, recall that the number of colors was $K$.

Decision variables¶

Let us use a $N \times K$ binary decision variable table $q$, where 0 and 1 denote which color to paint each vertex with. That is, $q_{v, k} = 1$ when vertex $v$ is painted with color $k$.

For example, when painting a vertex as follows, the corresponding binary variable table $q$ will look like the table below.

Index of vertex	0	1	2	3	4	5
Index of color	0	1	2	0	1	2

$q$	Color 0	Color 1	Color 2
Vertex 0	1	0	0
Vertex 1	0	1	0
Vertex 2	0	0	1
Vertex 3	1	0	0
Vertex 4	0	1	0
Vertex 5	0	0	1

Objective function¶

In this problem, we only need one solution that satisfies the condition, so we do not consider objective function.

Constraints¶

For $q$ to correspond to painting colors that satisfy the painting rule, the following conditions must be satisfied.

Condition 1: Each vertex is painted with exactly one color. That is, each row of $q$ has exactly one $1$.
Condition 2: Two vertices connected by an edge are not painted with the same color.

Condition 1 is a one-hot constraint on each row of $q$, so,

$$ \sum_{k = 0}^{K - 1} q_{v, k} = 1 \quad\text{for}\quad v \in V. $$

Here, $V$ is the vertex set of $G$.

The condition 2 is that the two vertices $(u, v)$ comprising the edge $E$ of $G$ have different colors, and written as

$$ q_{u, k} q_{v, k} = 0 \quad\text{for}\quad (u, v) \in E, \ k \in \{0, 1, \ldots, K-1\}. $$

Here, $E$ is the edge set of $G$.

If $q$ satisfies conditions 1 and 2, then $q$ corresponds to how to color the graph that satisfies the conditions.

Implementation¶

Using the problem and formulation described above, let us implement and solve the problem. First, we create $N\times K$ binary variables $q$ using BinarySymbolGenerator in Fixstars Amplify SDK.

In [ ]:

from amplify import VariableGenerator
    
gen = VariableGenerator()
q = gen.array("Binary", shape=(N, K))

Now, let us create a constraint corresponding to the condition 1. We will implement the one-hot constraint for each $q$ row as follows.

In [ ]:

from amplify import one_hot
    
constraint1 = one_hot(q, axis=1)

Then, we create a constraint condition corresponding to the condition 2. Condition 2 is that the two vertices connected by an edge are painted in different colors and

$q_{u, k} q_{v, k} = 0 \bigr((u, v) \in E, \ k \in \{0, 1, \ldots, K-1\}\bigl)$.

The above equation can be implemented as follows.

In [ ]:

from amplify import equal_to, sum as amplify_sum
    
constraint2 = amplify_sum(
    equal_to(q[u, k] * q[v, k], 0) for (u, v) in G.edges for k in range(K)
)

Now, we will convert the constructed constraints into an optimization model.

In [ ]:

from amplify import Model
    
model = Model(constraint1 + constraint2)

Let us set the client and execute the solver with Fixstars Amplify Annealing Engine (AE).

In [ ]:

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)

Since Amplify SDK automatically filters the solutions that satisfy the constraints, if the result is not empty, you know that there is a solution that satisfies the constraints.

In [ ]:

if len(result) == 0:
    print("No solution has been found.")
else:
    print("A solution has been found.")

Finally, let us visualize the solution.

In [ ]:

import numpy as np
    
color_list = ["C0", "C1", "C7"]
    
values = q.evaluate(result.best.values)
colors = [color_list[k] for k in np.where(values == 1)[1]]
    
nx.draw_networkx(G, node_size=600, font_color="w", node_color=colors, pos=pos)