dwave_networkx.algorithms.cover.min_vertex_cover#
- min_vertex_cover(G, sampler=None, lagrange=2.0, **sampler_args)[source]#
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.
- Parameters:
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.
- Returns:
vertex_cover – List of nodes that form a minimum vertex cover, as determined by the given sampler.
- Return type:
Examples
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]
Notes
Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.
References
https://en.wikipedia.org/wiki/Vertex_cover
https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization
[AL]Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, Volume 2, Article 5.