Warning
This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.
clique_removal¶

clique_removal
(G)[source]¶ Repeatedly remove cliques from the graph.
Results in a \(O(V/(\log V)^2)\) approximation of maximum clique & independent set. Returns the largest independent set found, along with found maximal cliques.
Parameters: G : NetworkX graph
Undirected graph
Returns: max_ind_cliques : (set, list) tuple
Maximal independent set and list of maximal cliques (sets) in the graph.
References
[R141] Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.