dwave_networkx.maximum_clique¶

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

Returns an approximate maximum clique. A clique in an undirected graph, G = (V, E), is a subset of the vertex set $$C \subseteq V$$ such that for every two vertices in C there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete (in some cases, the term clique may also refer to the subgraph). A maximum clique is a clique of the largest possible size in a given graph.

This function works by finding the maximum independent set of the compliment graph of the given graph G which is equivalent to finding maximum clique. It defines a QUBO with ground states corresponding to a maximum weighted independent set and uses the sampler to sample from it.

Parameters
• G (NetworkX graph) – The graph on which to find a maximum clique.

• 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

clique_nodes – List of nodes that form a maximum clique, 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

Maximum Clique on Wikipedia

Independent Set on Wikipedia

QUBO on Wikipedia

AL

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