Skip to main content
`Ctrl`+`K`

# maximal_independent_set

maximal_independent_set(G, nodes=None, seed=None)

  Returns a random maximal independent set guaranteed to contain a given set of nodes.

  An independent set is a set of nodes such that the subgraph of G induced by these nodes contains no edges. A maximal independent set is an independent set such that it is not possible to add a new node and still get an independent set.

  Parameters:
    G NetworkX graph
    nodes list or iterable

      Nodes that must be part of the independent set. This set of nodes must be independent.

    seed integer, random_state, or None (default)

      Indicator of random number generation state. See Randomness.

  Returns:
    indep_nodes list

      List of nodes that are part of a maximal independent set.

  Raises:
    NetworkXUnfeasible

      If the nodes in the provided list are not part of the graph or do not form an independent set, an exception is raised.

    NetworkXNotImplemented

      If `G` is directed.

  Notes

  This algorithm does not solve the maximum independent set problem.

  Examples

      >>> G = nx.path_graph(5)
      >>> nx.maximal_independent_set(G)
      [4, 0, 2]
      >>> nx.maximal_independent_set(G, [1])
      [1, 3]