A sufficiently fast algorithm for finding close to optimal clique trees

We offer an algorithm that finds a clique tree such that the size of the la rgest clique is at most (2 alpha + 1)k where k is the size of the largest c lique in a clique tree in which this size is minimized and or is the approx imation ratio of an alpha -approximation algorithm for the 3-way vertex cut problem. When alpha = 4/3, our algorithm's complexity is O(2(4.67k)n . pol y(n)) and it errs by a factor of 3.67 where poly(n) is the running time of linear programming. This algorithm is extended to find clique trees in whic h the state space of the largest clique is bounded. When k = O(log n), our algorithm yields a polynomial inference algorithm for Bayesian networks. (C ) 2001 Elsevier Science B.V. All rights reserved.