dimod.generators.maximum_independent_set#

maximum_independent_set(edges: Iterable[Tuple[Hashable, Hashable]], nodes: Iterable[Hashable] | None = None, *, strength: float = 2) → BinaryQuadraticModel[source]#

Generate a binary quadratic model encoding a maximum independent set problem.

Given a graph G, 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 the independent set with the most nodes.

Parameters:

  • edges – Edges of the graph.

  • nodes – Nodes of the graph.

  • strength – Strength of the quadratic biases. Must be strictly greater than 1 to enforce the independent set constraint.

Returns:

A binary quadratic model (BQM) with variables and interactions corresponding to nodes and edges.

Examples

Generate a maximum independent set BQM from a list of edges.

>>> dimod.generators.maximum_independent_set([(0, 1), (1, 2)])
BinaryQuadraticModel({0: -1.0, 1: -1.0, 2: -1.0}, {(1, 0): 2.0, (2, 1): 2.0}, 0.0, 'BINARY')

Generate a maximum independent set BQM from a list of edges and nodes.

>>> dimod.generators.maximum_independent_set([(0, 1)], [0, 1, 2])
BinaryQuadraticModel({0: -1.0, 1: -1.0, 2: -1.0}, {(1, 0): 2.0}, 0.0, 'BINARY')

Generate a maximum independent set BQM from a networkx.Graph.

>>> import networkx as nx
>>> G = nx.complete_graph(2)
>>> dimod.generators.maximum_independent_set(G.edges, G.nodes)
BinaryQuadraticModel({0: -1.0, 1: -1.0}, {(1, 0): 2.0}, 0.0, 'BINARY')