bron_kerbosch

iqm.applications.mis.bron_kerbosch(mis_problem, all_solutions=False)

Bron-Kerbosch algorithm for finding the maximum independent set.

The algorithm finds all maximal cliques in a graph recursively. Cliques in complement graph correspond to independent sets in the problem graph. For details see find_cliques — NetworkX documentation (and the references therein). If all_solutions is False (default), return one maximum independent set as a bitstring. If all_solutions is True, return a set of bitstrings corresponding to all maximum independent sets found (not all maximal independent sets).

Parameters:

• mis_problem (MISInstance | Graph) – A problem instance of maximum independent set or a Graph.

• all_solutions (bool) – Should the algorithm return all solutions?

Returns:

A bitstring solution.

Return type:

str | set[str]