dwave_networkx.maximum_weighted_independent_set

maximum_weighted_independent_set(G, weight=None, sampler=None, lagrange=2.0, **sampler_args)[source]

Returns an approximate maximum weighted independent set.

Defines a QUBO with ground states corresponding to a maximum weighted 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 maximum total node weight.

Parameters:
  • G (NetworkX graph) – The graph on which to find a maximum cut weighted independent set.
  • 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 (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 weighted independent set, 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.

References

Independent Set on Wikipedia

QUBO on Wikipedia

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