clique_number(G, sampler=None, lagrange=2.0, **sampler_args)¶
Returns the number of vertices in the maximum clique of a graph. A maximum clique is a clique of the largest possible size in a given graph. The clique number omega(G) of a graph G is the number of vertices in a maximum clique in G. The intersection number of G is the smallest number of cliques that together cover all edges of G.
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.
- 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.
clique_nodes – List of nodes that form a maximum clique, as determined by the given sampler.
Samplers by their nature may not return the optimal solution. This function does not attempt to confirm the quality of the returned sample.