Skip to main content
`Ctrl`+`K`

# clique_removal

clique_removal(G)

  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

  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.

  Examples

      >>> G = nx.path_graph(10)
      >>> nx.approximation.clique_removal(G)
      ({0, 2, 4, 6, 9}, [{0, 1}, {2, 3}, {4, 5}, {6, 7}, {8, 9}])