Unfortunately, there is a big catch - this inference algorithm works only for belief networks that can be expressed as acyclic graphs. If the graph is not acyclic, the computational cost of the inference algorithm is much larger (IIRC, it is exponential in the size of the largest clique in the graph).

Actually, all valid belief networks are acyclic graphs. What you're thinking of is that inference in tree-structured Bayes nets can be solved in polynomial time (e.g. using the Belief Propagation algorithm), whereas for non-tree structured graphs there is no such polynomail time algorithm currently known (iirc it has been proved that inference in Bayes nets is NP complete in general). Loopy Belief Propagation and variational methods can be used as non-deterministic approximate inference algorithms in non-tree structured Bayes nets.