Warning

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

# networkx.algorithms.approximation.clique.clique_removal¶

clique_removal(G)[source]

Repeatedly remove cliques from the graph.

Results in a $$O(|V|/(\log |V|)^2)$$ approximation of maximum clique and independent set. Returns the largest independent set found, along with found maximal cliques.

Parameters: G (NetworkX graph) – Undirected graph max_ind_cliques – 2-tuple of Maximal Independent Set and list of maximal cliques (sets). (set, list) tuple

References

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