dwave_networkx.algorithms.cover.min_weighted_vertex_cover

min_weighted_vertex_cover(G, weight=None, sampler=None, lagrange=2.0, **sampler_args)

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

Return type

list

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 [AL]