Finding Minimal Separators in LWF Chain Graphs


Mohammad Ali Javidian, Marco Valtorta ;
Proceedings of the Ninth International Conference on Probabilistic Graphical Models, PMLR 72:193-200, 2018.


We address the problem of finding a minimal separator in a LWF chain graph, namely, finding a set $Z$ of nodes that separates a given non-adjacent pair of nodes such that no proper subset of $Z$ separates that pair. We analyze several versions of this problem and offer polynomial time algorithms for each. These include finding a minimal separator from a restricted set of nodes, finding a minimal separator for two given disjoint sets, and testing whether a given separator is minimal.

Related Material