is_minimal_d_separator(G, x, y, z, *, included=None, restricted=None)[source]#

Determine if z is a minimal d-separator for x and y.

A d-separator, z, in a DAG is a set of nodes that blocks all paths from nodes in set x to nodes in set y. A minimal d-separator is a d-separator z such that removing any subset of nodes makes it no longer a d-separator.

Note: This function checks whether z is a d-separator AND is minimal. One can use the function is_d_separator to only check if z is a d-separator. See examples below.


A NetworkX DAG.

xnode | set

A node or set of nodes in the graph.

ynode | set

A node or set of nodes in the graph.

znode | set

The node or set of nodes to check if it is a minimal d-separating set. The function is_d_separator() is called inside this function to verify that z is in fact a d-separator.

includedset | node | None

A node or set of nodes which must be included in the found separating set, default is None, which means the empty set.

restrictedset | node | None

Restricted node or set of nodes to consider. Only these nodes can be in the found separating set, default is None meaning all nodes in G.


Whether or not the set z is a minimal d-separator subject to restricted nodes and included node constraints.


Raises a NetworkXError if the input graph is not a DAG.


If any of the input nodes are not found in the graph, a NodeNotFound exception is raised.


This function works on verifying that a set is minimal and d-separating between two nodes. Uses criterion (a), (b), (c) on page 4 of [1]. a) closure(x) and y are disjoint. b) z contains all nodes from included and is contained in the restricted nodes and in the union of ancestors of x, y, and included. c) the nodes in z not in included are contained in both closure(x) and closure(y). The closure of a set is the set of nodes connected to the set by a directed path in G.

The complexity is \(O(m)\), where \(m\) stands for the number of edges in the subgraph of G consisting of only the ancestors of x and y.

For full details, see [1].


[1] (1,2)

van der Zander, Benito, and Maciej Liśkiewicz. “Finding minimal d-separators in linear time and applications.” In Uncertainty in Artificial Intelligence, pp. 637-647. PMLR, 2020.


>>> G = nx.path_graph([0, 1, 2, 3], create_using=nx.DiGraph)
>>> G.add_node(4)
>>> nx.is_minimal_d_separator(G, 0, 2, {1})
>>> # since {1} is the minimal d-separator, {1, 3, 4} is not minimal
>>> nx.is_minimal_d_separator(G, 0, 2, {1, 3, 4})
>>> # alternatively, if we only want to check that {1, 3, 4} is a d-separator
>>> nx.is_d_separator(G, 0, 2, {1, 3, 4})