Skip to main content
`Ctrl`+`K`

# is_minimal_d_separator

is_minimal_d_separator(G, x, y, z, *, included=None, restricted=None)

  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:
    G nx.DiGraph

      A NetworkX DAG.

    x node | set

      A node or set of nodes in the graph.

    y node | set

      A node or set of nodes in the graph.

    z node | 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.

    included set | 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.

    restricted set | 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)
      >>> G.add_node(4)
      >>> nx.is_minimal_d_separator(G, 0, 2, {1})
      True
      >>> # since {1} is the minimal d-separator, {1, 3, 4} is not minimal
      >>> nx.is_minimal_d_separator(G, 0, 2, {1, 3, 4})
      False
      >>> # 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})
      True