Proving the NP-completeness of optimal moral graph triangulation
Moral graphs were introduced in the 1980s as an intermediate step when transforming a Bayesian network to a junction tree, on which exact belief propagation can be efficiently done. The moral graph of a Bayesian network can be trivially obtained by connecting non-adjacent parents for each node in the Bayesian network and dropping the direction of each edge. Perhaps because the moralization process looks simple, there has been little attention on the properties of moral graphs and their impact in belief propagation on Bayesian networks. This paper addresses the mistaken claim that it has been previously proved that optimal moral graph triangulation with the constraints of minimum fill-in, treewidth or total states is NP-complete. The problems are in fact NP-complete, but they have not previously been proved. We now prove these.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An Algebraic Approach to Moralisation and Triangulation of Probabilistic Graphical Models
Moralisation and Triangulation are transformations allowing to switch between different ways of factoring a probability distribution into a graphical model. Moralisation allows to view a Bayesian network (a directed mode…
Bayesian Networks, Markov Networks, Moralisation, Triangulation: a Categorical Perspective
Moralisation and Triangulation are transformations allowing to switch between different ways of factoring a probability distribution into a graphical model. Moralisation allows to view a Bayesian network (a directed mode…
A Dominance Argument Against Incompleteness
This article presents a new argument against many forms of moral and prudential value incompleteness. The argument relies on two central principles: (i) a weak "negative dominance" principle, to the effect that Lottery 1…
Bound and Conquer: Improving Triangulation by Enforcing Consistency
We study the accuracy of triangulation in multi-camera systems with respect to the number of cameras. We show that, under certain conditions, the optimal achievable reconstruction error decays quadratically as more camer…
Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we consider the constraint that the network or…