Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

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
GNetworkX graph

Undirected graph

Returns
max_ind_cliques(set, list) tuple

2-tuple of Maximal Independent Set and list of maximal cliques (sets).

Raises
NetworkXNotImplemented

If the graph is directed or is a multigraph.

References

1

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