# 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
N = 6 # Number of vertices of the graph
K = 2 # Number of colors
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [
(0, 1),
(0, 2),
(1, 2),
(1, 3),
(1, 4),
(2, 3),
(2, 5),
(3, 4),
(3, 5),
(4, 5),
]
G.add_edges_from(edge_list)
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 VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", shape=(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 import one_hot
constraint1 = one_hot(q, axis=1)
```

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 import equal_to, sum as amplify_sum
constraint2 = amplify_sum(
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 an optimization model.

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

Let us set the client and execute the solver with Fixstars 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)
```

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.

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

Lastly, let us visualize the solution.

```
import numpy as np
values = q.evaluate(result.best.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)
```