dwave_networkx.algorithms.independent_set.maximum_independent_set

maximum_independent_set(G, sampler=None, **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) –
  • 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.
  • sampler_args – Additional keyword parameters are passed to the sampler.
Returns:

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

list

Examples

>>> G = nx.path_graph(5)
>>> dnx.maximum_independent_set(G, sampler)
[0, 2, 4]

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/Independent_set_(graph_theory)

https://en.wikipedia.org/wiki/Quadratic_unconstrained_binary_optimization

References

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