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.

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.

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

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

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.

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.

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.