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 , a vertex cover of is a subset of the vertices of such that contains at least one endpoint of any edge of . The problem of finding the vertex cover of 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 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 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 to be vertex-covered, 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 .
Formulation¶
Let be the number of vertices in hereafter.
Decision variables¶
Let each of binary variables be associated with each vertex to indicate whether the vertex is included in the vertex cover . The variable is if its corresponding vertex is included in and if not.
For example, when is the set of orange vertices as in the figure below, the decision variable would be as in the below table.
Index of vertex | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
1 | 0 | 1 | 0 | 1 | 0 |
Objective function¶
Since the number of elements in should be as small as possible, the objective function is .
Constraints¶
For to represent a vertex cover, we need the following constraints.
- Condition 1: For each edge of , either or is contained in .
Since this is a condition that either the binary variable corresponding to or the binary variable corresponding to is ,
Here, is an edge set of . Conversely, when condition 1 holds, clearly is a vertex covering .
Implementation¶
Using the problem and formulation defined above, let us implement and solve the problem. First,
create as
many binary variables 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 , and we can compute it by summing .
cost = q.sum()
Create the constraint condition corresponding to the condition 1. The condition 1 implies that for each edge of , one of the two vertices is contained in and is represented by .
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)