Yang Li, Lloyd Allison and Kevin B. Korb

Theoretical Computer Science, vol.885, pp.77-90, doi:10.1016/j.tcs.2021.06.024, 11 September 2021

Abstract: A family of Markov blankets, if learned purely as a set of subsets of variables, may not be consistent with any Bayesian network. This inconsistency may have a negative impact on Markov blanket-based structure learning. In this paper, we propose checking Markov blanket consistency using graph morality. We define an alternative concept of moral graph – weak recursive simpliciality – without relying on Bayesian networks. Although it is NP-complete to decide if an undirected graph in general is moral, we propose linear and quadratic time algorithms for deciding morality for maximum degree 3 and 4 graphs respectively. In addition, we prove that the problem remains NP-complete for graphs with maximum degree higher than 4, hence there are no remaining unknown complexities for this kind of problem.