Approximate belief updating in max-2-connected Bayes networks is NP-hard
A max-2-connected Bayes network is one where there are at most 2 distinct directed paths between any two nodes. We show that even for this restricted topology, null-evidence belief updating is hard to approximate. (C) 2009 Elsevier B.V. All rights reserved.
bayes network complexity max-k-connected