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:
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
[AL]Lucas, A. (2014). Ising formulations of many NP problems. Frontiers in Physics, Volume 2, Article 5.