min_vertex_cover(G, sampler=None, lagrange=2.0, **sampler_args)¶
Returns an approximate minimum vertex cover.
Defines a QUBO with ground states corresponding to a minimum vertex cover and uses the sampler to sample from it.
A vertex cover is a set of vertices such that each edge of the graph is incident with at least one vertex in the set. A minimum vertex cover is the vertex cover of smallest size.
G (NetworkX graph) – The graph on which to find a minimum vertex cover.
sampler – A binary quadratic model sampler. A sampler is a process that samples from low energy states in models defined by an Ising equation or a Quadratic Unconstrained Binary Optimization Problem (QUBO). A sampler is expected to have a ‘sample_qubo’ and ‘sample_ising’ method. A sampler is expected to return an iterable of samples, in order of increasing energy. If no sampler is provided, one must be provided using the set_default_sampler function.
lagrange (optional (default 2)) – Lagrange parameter to weight constraints versus objective.
sampler_args – Additional keyword parameters are passed to the sampler.
vertex_cover – List of nodes that form a minimum vertex cover, as determined by the given sampler.
- Return type
This example uses a sampler from dimod to find a minimum vertex cover for a Chimera unit cell. Both the horizontal (vertices 0,1,2,3) and vertical (vertices 4,5,6,7) tiles connect to all 16 edges, so repeated executions can return either set.
>>> import dwave_networkx as dnx >>> import dimod >>> sampler = dimod.ExactSolver() # small testing sampler >>> G = dnx.chimera_graph(1, 1, 4) >>> G.remove_node(7) # to give a unique solution >>> dnx.min_vertex_cover(G, sampler, lagrange=2.0) [4, 5, 6]
Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.
Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, Volume 2, Article 5.