## The difficulty of being moral

#### 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.