grinpy.invariants.independence.max_independent_set

grinpy.invariants.independence.max_independent_set(G)

Return a largest independent set of nodes in G.

The method used is a modified brute force search. The search starts with subsets of G with cardinality equal to the annihilation number of G, which was shown by Pepper to be an upper bound for the independence number of a graph, and then continues checking smaller subsets until a maximum independent set is found.

Parameters:G (NetworkX graph) – An undirected graph.
Returns:A list of nodes comprising a largest independent set in G.
Return type:list