# Graph Coloring Problem

Here we show how to solve graph coloring problems using JijZept and JijModeling. This problem is also mentioned in 6.1. Graph Coloring on Lucas, 2014, "Ising formulations of many NP problems".

## What is the graph coloring problem?​

In this problem, we color different colors to the two vertices on the same edge in a given graph. This problem is related to the famous four-color theorem which we can color the map with four colors. The picture below is a schematic picture of this theorem. We can color every object in the figures with four colors. If we can use only 3 colors, which is called 3-coloring, this is one of the famous NP-complete problems.

### Example​

Let's consider the following undirected graph consisting of 6 vertices below as an example. We can color this graph in three colors as follows. No edge connects two vertices of the same color exist.

### Generalization​

Next, we generalize the above example and express it in a mathematical model. We consider coloring an undirected graph $G=(V, E)$ with $N$ colors and introduce variables $x_{v, n}$ which are 1 if vertex $v$ is colored with $n$ and 0 otherwise.

Constraint: the vertices must be painted with one color

This problem can not allow us to color a vertex with two colors.

$\sum_{n=0}^{N-1} x_{v, n} = 1 \quad (\forall v \in V) \tag{1}$

Objective function: we minimize the number of edges that connect two vertices of the same color

$\min \quad \sum_{n=0}^{N-1} \sum_{(uv) \in E} x_{u, n} x_{v, n} \tag{2}$

where E is a set of edges on graph $G$. This objective function is quite complicated. Let us see the table below.

$x_{u,n}$$x_{v,n}$$x_{u,n}x_{v,n}$
000
000
100
111

As we defined above if vertex$u$ is colored by $n$, $x_{u,n}=1$, so only when both $x_{u,n}$ and $x_{v,n}$ are 1, $x_{u,n}x_{v,n} = 1$ in the above table, and 0 otherwise. When two vertices on every edge have different colors, the value of this objective function becomes 0. Thus, this objective function is an indicator of how much graph coloring has been achieved.

## Modeling by JijModeling​

Next, we show an implementation of the above mathematical model in JijModeling. We first define variables for the mathematical model.

import jijmodeling as jm# define variablesV = jm.Placeholder('V')E = jm.Placeholder('E', ndim=2)N = jm.Placeholder('N')x = jm.BinaryVar('x', shape=(V, N))n = jm.Element('i', belong_to=(0, N))v = jm.Element('v', belong_to=(0, V))e = jm.Element('e', belong_to=E)

V=jm.Placeholder('V') represents the number of vertices. We denote E=jm.Placeholder('E', ndim=2) a set of edges. Also N is the number of colors. Then, we define a two-dimensional list of binary variables x=jm.BinaryVar('x', shape=(V, N)) Finary, we set the subscripts n and v used in the mathematical model. e represents the variable for edges. e and e mean the vertex $u$ and $v$ on the edge, respectively.

### Constraint​

We implement a constraint Equation (1).

# set problemproblem = jm.Problem('Graph Coloring')# set one-hot constraint that each vertex has only one colorconst = x[v, :].sum()problem += jm.Constraint('one-color', const==1, forall=v)

x[v, :].sum() is syntactic sugar of sum(n, x[v, n]).

### Objective function​

Next, we implement an objective function Equation (2)

# set objective function: minimize edges whose vertices connected by edges are the same colorsum_list = [n, e]problem += jm.sum(sum_list, x[e, n]*x[e, n])

We can write $\sum_n \sum_e$ as sum([n, e], ...). We can easily formulate the summation over nodes in edges with JijModeling.

Let's display the implemented mathematical model in Jupyter Notebook.

problem

$\begin{array}{cccc}\text{Problem:} & \text{Graph Coloring} & & \\& & \min \quad \displaystyle \sum_{i = 0}^{N - 1} \sum_{e \in E} x_{e_{0}, i} \cdot x_{e_{1}, i} & \\\text{{s.t.}} & & & \\ & \text{one-color} & \displaystyle \sum_{\ast_{1} = 0}^{N - 1} x_{v, \ast_{1}} = 1 & \forall v \in \left\{0,\ldots,V - 1\right\} \\\text{{where}} & & & \\& x & 2\text{-dim binary variable}\\\end{array}$

## Prepare an instance​

We prepare a graph using NetworkX. Here we create random graph with 12 vertices.

import networkx as nx# set the number of verticesinst_V = 12# set the number of colorsinst_N = 4# create a random graphinst_G = nx.gnp_random_graph(inst_V, 0.4)# get information of edgesinst_E = [list(edge) for edge in inst_G.edges]instance_data = {'V': inst_V, 'N': inst_N, 'E': inst_E}

In this code, the number of vertices in the graph and the number of colors are 12 and 4, respectively.

## Solve by JijZept's SA​

We solve this problem using JijZept JijSASampler. We also use the parameter search function by setting search=True.

import jijzept as jz# set samplersampler = jz.JijSASampler(config="config.toml")# solve problemmultipliers = {"one-color": 0.5}results = sampler.sample_model(problem, instance_data, multipliers, num_reads=100, search=True)

# Visualize solution

In the end, we extract the lowest energy solution among the feasible solutions and visualize it. We obtain the feasible coloring for this graph as you can see.

import matplotlib.pyplot as pltimport numpy as np# extract feasible solutionfeasibles = results.feasible()if feasibles.evaluation.objective.size == 0:    print('No feasible solution found ...')else:    objectives = np.array(feasibles.evaluation.objective)    lowest_index = np.argmin(objectives)    print("Objective: "+str(feasibles.evaluation.objective[lowest_index]))    # get indices of x = 1    indices, _, _ = feasibles.record.solution['x'][lowest_index]    # get vertex number and color    vertices, colors = indices    # sort lists by vertex number    zip_lists = zip(vertices, colors)    zip_sort = sorted(zip_lists)    sorted_vertices, sorted_colors = zip(*zip_sort)    # initialize vertex color list    node_colors = [-1] * len(vertices)    # set color list for visualization    colorlist = ['gold', 'violet', 'limegreen', 'darkorange']    # set vertex color list    for i, j in zip(sorted_vertices, sorted_colors):        node_colors[i] = colorlist[j]    # make figure    nx.draw_networkx(inst_G, node_color=node_colors, with_labels=True)    plt.show()
Objective: 0.0 