Independent Set#

An independent set is a set of a graph’s vertices with no edge connecting any of its member pairs.

image

Independent sets for a Chimera unit cell: the nodes of both the blue set of vertices (the horizontal tile of the Chimera unit cell) and the red set (vertical tile) are independent sets of the graph, with no blue node adjacent to another blue node and likewise for red nodes.#

maximum_weighted_independent_set(G[, ...])

Returns an approximate maximum weighted independent set.

maximum_independent_set(G[, sampler, lagrange])

Returns an approximate maximum independent set.

is_independent_set(G, indep_nodes)

Determines whether the given nodes form an independent set.

Helper Functions#

maximum_weighted_independent_set_qubo(G[, ...])

Return the QUBO with ground states corresponding to a maximum weighted independent set.