dwave.graphs.algorithms.cover.min_vertex_cover#

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

Return type:

list

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.graphs
>>> import dimod
>>> sampler = dimod.ExactSolver()  # small testing sampler
>>> G = dwave.graphs.chimera_graph(1, 1, 4)
>>> G.remove_node(7)  # to give a unique solution
>>> dwave.graphs.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

Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, Volume 2, Article 5.