#
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
N = 6 # Number of graph vertices
G = nx.Graph()
G.add_nodes_from(range(N))
edge_list = [
(0, 1),
(0, 4),
(0, 5),
(1, 2),
(1, 4),
(2, 3),
(2, 4),
(2, 5),
(3, 4),
(4, 5),
]
G.add_edges_from(edge_list)
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 VariableGenerator
gen = VariableGenerator()
q = gen.array("Binary", 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 import equal_to, sum as amplify_sum
constraints = amplify_sum(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 an optimization 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.

```
model = cost + constraints
```

Let us set the client and solve the logical model with Fixstars Amplify Annealing Engine (AE). 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.

```
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)
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.

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