networkx.algorithms.mis.maximal_independent_set

maximal_independent_set(G, nodes=None, seed=None)[source]

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
GNetworkX graph
nodeslist or iterable

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

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

Returns
indep_nodeslist

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]