dwave.graphs.algorithms.cover.min_weighted_vertex_cover#
- min_weighted_vertex_cover(G, sampler, weight=None, lagrange=2.0, **sampler_args)[source]#
Returns an approximate minimum weighted vertex cover.
Defines a QUBO with ground states corresponding to a minimum weighted 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 weighted vertex cover is the vertex cover of minimum total node weight.
- Parameters:
G (NetworkX graph)
weight (string, optional (default None)) – If None, every node has equal weight. If a string, use this node attribute as the node weight. A node without this attribute is assumed to have max weight.
sampler (
dimod.Sampler) – A dimod sampler.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 the form a the minimum weighted vertex cover, as determined by the given sampler.
- Return type:
Notes
Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.
https://en.wikipedia.org/wiki/Vertex_cover
https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization
References
Based on the formulation presented in [Luc2014].