# An Algorithm for Finding Minimum d-Separating Sets in Belief Networks

arXiv: https://arxiv.org/abs/1302.3549 · HTML: https://mlsanity.com/paper/1302.3549/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2013.

## Built on by (most cited first, 5 of 5)

- [Causal Imitability Under Context-Specific Independence Relations](https://mlsanity.com/paper/2306.00585/) (2023)
- [Invariant Ancestry Search](https://mlsanity.com/paper/2202.00913/) (2022)
- [Causal Discovery in Mixtures of Populations](https://mlsanity.com/paper/2311.07454/) (2023)
- [A note on efficient minimum cost adjustment sets in causal graphical models](https://mlsanity.com/paper/2201.02037/) (2022)
- [Influence-Augmented Local Simulators: A Scalable Solution for Fast Deep RL in Large Networked Systems](https://mlsanity.com/paper/2202.01534/) (2022)

## Abstract (arXiv)

The criterion commonly used in directed acyclic graphs (dags) for testing graphical independence is the well-known d-separation criterion. It allows us to build graphical representations of dependency models (usually probabilistic dependency models) in the form of belief networks, which make easy interpretation and management of independence relationships possible, without reference to numerical parameters (conditional probabilities). In this paper, we study the following combinatorial problem: finding the minimum d-separating set for two nodes in a dag. This set would represent the minimum information (in the sense of minimum number of variables) necessary to prevent these two nodes from influencing each other. The solution to this basic problem and some of its extensions can be useful in several ways, as we shall see later. Our solution is based on a two-step process: first, we reduce the original problem to the simpler one of finding a minimum separating set in an undirected graph, and second, we develop an algorithm for solving it.