dwave_networkx.is_independent_set

is_independent_set(G, indep_nodes)

Determines whether the given nodes form an independent set.

An independent set is a set of nodes such that the subgraph of G induced by these nodes contains no edges.

Parameters:

• G (NetworkX graph) – The graph on which to check the independent set.

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

Returns:

is_independent – True if indep_nodes form an independent set.

Return type:

bool

Example

This example checks two sets of nodes, both derived from a single Chimera unit cell, for an independent set. The first set is the horizontal tile’s nodes; the second has nodes from the horizontal and verical tiles.

>>> import dwave_networkx as dnx
>>> G = dnx.chimera_graph(1, 1, 4)
>>> dnx.is_independent_set(G, [0, 1, 2, 3])
True
>>> dnx.is_independent_set(G, [0, 4])
False