# Example
NP
problems published in A. Lucas, *Front. Phys.* (2014) - Clique cover problem¶

This example code implements the **clique cover 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)

## Clique cover problem¶

Given a graph $G$ and an integer $K$, **clique cover problem** is the problem to
determine
whether the vertices of $G$ can be painted with a $K$ color so that every pair of vertices of the same
color is connected by an edge.

For example, the following graph shows that it is possible to cover $G$ with $2$ colors (cliques) because all three blue vertices are connected by edges, and all three orange vertices are also connected by edges.

Here, we create a program that uses Fixstars Amplify to search for a way to paint the vertices. The formulation follows the one in section 6.2 of A. Lucas, Front. Phys. (2014).

## Problem definition¶

First, for example, let us create a graph $G$ using NetworkX. Also, let $K$, the number of colors, be $2$.

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

The resulting graph is the same as the one shown in the introduction. Therefore, the condition is satisfied by painting the vertices $0$, $1$, and $2$ in one color and the vertices $3$, $4$, and $5$ in the other color.

## Formulation¶

Let $N$ be the number of vertices of $G$ below.

### Decision variables¶

Create a binary decision variable table $q$ of $N \times K$, where each vertex is painted with a color specified by a corresponding decision variable. When vertex $i$ is painted with the $j$-th color, the binary variable in the $i$ row $j$ column of $q$ is $1$.

For example, when vertices $0$, $1$, and $2$ are painted with the $0$th color and vertices $3$, $4$, and $5$ are painted with the $1$st color, the variable table $q$ is as follows.

$q$ | 0th color | 1st color |
---|---|---|

Vertex 0 | 1 | 0 |

Vertex 1 | 1 | 0 |

Vertex 2 | 1 | 0 |

Vertex 3 | 0 | 1 |

Vertex 4 | 0 | 1 |

Vertex 5 | 0 | 1 |

### Objective function¶

Since the clique cover problem is to find one that satisfies the condition, No objective function is considered.

### Constraints¶

For $G$ to be covered by $K$ cliques according to $q$ and the corresponding coloring scheme, we need the following constraints.

- Condition 1 : Each vertex of $G$ is painted with exactly a single color.
- Condition 2: Vertices of the same color are always connected by an edge.

Condition 1 is the constraint that there is precisely one $1$ in each row, and we can express this as:

$$ \sum_{j = 0}^{K-1} q_{i, j} = 1 \quad \text{for} \quad i \in \{0, 1, \ldots, N-1\}. $$

Also, considering the contraposition of condition 2, condition 2 is rephrased as "$2$ vertices not connected by an edge are not painted in the same color".

The condition can be written as:

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

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

## 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.

```
from amplify import BinarySymbolGenerator
gen = BinarySymbolGenerator()
q = gen.array(N, K)
```

Next, we construct the constraint corresponding to condition 1. Condition 1 is condition that there
is
only one 1 in each row of $q$, so we can use `one_hot`

to express this condition.

```
from amplify.constraint import one_hot
constraint1 = [one_hot(q[i, :]) for i in range(N)]
```

Then, let us construct a constraint condition corresponding to the condition 2. The condition 2 is, $q_{u, j} q_{v, j} = 0 \bigl((u, v) \notin E, \ j \in \{0, 1, \ldots, K - 1\}\bigr)$.

```
from amplify.constraint import equal_to
constraint2 = [
equal_to(q[u, j] * q[v, j], 0)
for u in range(N)
for v in range(N)
for j in range(K)
if u < v and (u, v) not in G.edges and (v, u) not in G.edges
]
```

Now, we combine the abovementioned constraints and convert them into a logical model.

```
from amplify import BinaryQuadraticModel
model = BinaryQuadraticModel(sum(constraint1) + sum(constraint2))
```

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

```
from amplify.client import FixstarsClient
from amplify import Solver
client = FixstarsClient()
# client.token = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" # If you use Amplify in a local environment or Google Colaboratory, enter your Amplify API token.
client.parameters.timeout = 1000
# Define and execute the solver
solver = Solver(client)
result = solver.solve(model)
```

Since `Solver`

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.

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

Lastly, let us visualize the solution.

```
values = q.decode(result[0].values)
colors = [f"C{i}" for i in np.where(values == 1)[1]]
nx.draw_networkx(G, node_size=600, node_color=colors, font_color="w", pos=pos)
```