7.1.3.2. networkx.algorithms.approximation.clique.clique_removal¶

networkx.algorithms.approximation.clique.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

[R451]

Boppana, R., & Halldórsson, M. M. (1992). Approximating maximum independent sets by excluding subgraphs. BIT Numerical Mathematics, 32(2), 180–196. Springer.