min_weighted_vertex_cover(G, weight=None, sampler=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.

  • 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 – 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 the form a the minimum weighted vertex cover, as determined by the given sampler.

Return type:



Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.




Based on the formulation presented in [AL]