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

This example code implements the **minimum vertex 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)
- 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)

## Minimum vertex cover problem¶

For a graph $G$, a **vertex cover** of $G$ is a subset $R$ of the vertices of $G$ such
that
$R$ contains at least one endpoint of any edge of $G$. The problem of finding the vertex cover of $G$
with
the smallest number of elements is called the **minimum vertex cover problem**.

For example, in the following graph, the set of orange vertices is a vertex cover. Observe that any edge of the graph $G$ is connected to an orange vertex.

This example program uses Fixstars Amplify to solve the minimum vertex cover problem. The formulation follows that of Sec. 4.3 of A. Lucas, Front. Phys. (2014).

## Problem definition¶

We will define a graph $G$ using NetworkX to demonstrate the minimum vertex cover problem with Fixstars Amplify.

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

As mentioned earlier, a set of vertices 0, 2, and 4 is vertex-covered. Also, for a set $R$ to be vertex-covered, $R$ must contain either vertex 0 or vertex 1, either vertex 2 or vertex 3, and either vertex 4 or vertex 5, so the minimum number of elements in the vertex cover is $3$.

## Formulation¶

Let $N$ be the number of vertices in $G$ hereafter.

### Decision variables¶

Let each of $N$ binary variables $q$ be associated with each vertex to indicate whether the vertex is included in the vertex cover $R$. The variable is $1$ if its corresponding vertex is included in $R$ and $0$ if not.

For example, when $R$ is the set of orange vertices as in the figure below, the decision variable $q$ would be as in the below table.

Index of vertex | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|

$q$ | 1 | 0 | 1 | 0 | 1 | 0 |

### Objective function¶

Since the number of elements in $R$ should be as small as possible, the objective function is $\displaystyle \sum_{v = 0}^{N - 1}q_v$.

### Constraints¶

For $q$ to represent a vertex cover, we need the following constraints.

- Condition 1: For each edge $(u, v)$ of $G$, either $u$ or $v$ is contained in $R$.

Since this is a condition that either the binary variable corresponding to $u$ or the binary variable corresponding to $v$ is $1$,

$$ (1 - q_u) (1 - q_v) = 0 \quad \text{for} \quad (u, v) \in E. $$

Here, $E$ is an edge set of $G$. Conversely, when condition 1 holds, clearly $R$ is a vertex covering $G$.

## Implementation¶

Using the problem and formulation defined above, let us implement and solve the problem. First,
create as
many binary variables $q$ as subsets are using the `BinarySymbolGenerator`

in Fixstars
Amplify
SDK.

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

As mentioned earlier, the objective function is the number of elements in $R$, and we can compute it by summing $q$.

```
cost = q.sum()
```

Create the constraint condition corresponding to the condition 1. The condition 1 implies that for each edge of $G$, one of the two vertices is contained in $R$ and is represented by $(1 - q_u) (1 - q_v) = 0 ,\:\: (u, v) \in E$.

```
from amplify.constraint import equal_to
constraint = [equal_to((1 - q[u]) * (1 - q[v]), 0) for u, v in G.edges]
```

The objective function and constraints implemented above are combined and converted into a logical model. Although not necessary in this case, it may be required to multiply the constraint weight, depending on the problem setup. The basic idea is to estimate and determine a value for the weight approximately equal to or slightly more significant than the possible values of the objective function.

```
from amplify import BinaryQuadraticModel
model = BinaryQuadraticModel(cost + sum(constraint))
```

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

automatically filters the solutions that satisfy the constraints, if the
`result`

is not empty, you know that there is a solution that meets the constraints.

```
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)
if len(result) == 0:
print("No solution has been found.")
else:
print("A solution has been found.")
```

Finally, let us visualize the result. We can see that the selected vertices form the minimum vertex cover. You can try to solve the same problem for different graph shapes.

```
import matplotlib.pyplot as plt
values = q.decode(result[0].values)
colors = ["C1" if value == 1 else "C0" for value in values]
nx.draw_networkx(G, node_size=600, font_color="w", node_color=colors, pos=pos)
```