dwave.graphs.algorithms.independent_set.maximum_independent_set#

maximum_independent_set(G, sampler, lagrange=2.0, **sampler_args)[source]#

Returns an approximate maximum independent set.

Defines a QUBO with ground states corresponding to a maximum independent set and uses the sampler to sample from it.

An independent set is a set of nodes such that the subgraph of G induced by these nodes contains no edges. A maximum independent set is an independent set of largest possible size.

Parameters:

  • G (NetworkX graph) – The graph on which to find a maximum cut independent set.

  • sampler (dimod.Sampler) – A dimod sampler.

  • lagrange (optional (default 2)) – Lagrange parameter to weight constraints (no edges within set) versus objective (largest set possible).

  • sampler_args – Additional keyword parameters are passed to the sampler.

Returns:

indep_nodes – List of nodes that form a maximum independent set, as determined by the given sampler.

Return type:

list

Example

This example uses a sampler from dimod to find a maximum independent set for a graph of a Chimera unit cell created using the chimera_graph() function.

>>> import dimod
>>> sampler = dimod.SimulatedAnnealingSampler()
>>> G = dwave.graphs.chimera_graph(1, 1, 4)
>>> indep_nodes = dwave.graphs.maximum_independent_set(G, sampler)

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

Independent Set on Wikipedia

QUBO on Wikipedia

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