Approximate belief updating in max-2-connected Bayes networks is NP-hard Original Research Article

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.