find_minimal_d_separator#

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

Returns a minimal d-separating set between x and y if possible

A d-separating set in a DAG is a set of nodes that blocks all paths between the two sets of nodes, x and y. This function constructs a d-separating set that is “minimal”, meaning no nodes can be removed without it losing the d-separating property for x and y. If no d-separating sets exist for x and y, this returns None.

In a DAG there may be more than one minimal d-separator between two sets of nodes. Minimal d-separators are not always unique. This function returns one minimal d-separator, or None if no d-separator exists.

Uses the algorithm presented in [1]. The complexity of the algorithm 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].

Parameters:

Ggraph: A networkx DAG.
xset | node: A node or set of nodes in the graph.
yset | node: A node or set of nodes in the graph.
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:

zset | None: The minimal d-separating set, if at least one d-separating set exists, otherwise None.

Raises:

NetworkXError: Raises a NetworkXError if the input graph is not a DAG or if node sets x, y, and included are not disjoint.
NodeNotFound: If any of the input nodes are not found in the graph, a NodeNotFound exception is raised.

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.