# is_minimal_d_separator#

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.

Parameters:
Gnx.DiGraph

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.

Returns:
bool

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

Raises:
NetworkXError

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

NodeNotFound

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

Notes

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].

References

[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.

Examples

>>> G = nx.path_graph([0, 1, 2, 3], create_using=nx.DiGraph)