  There has been great interest in identifying tractable subclasses of NP
complete problems and designing efficient algorithms for these tractable
classes. Constraint satisfaction and Bayesian network inference are two
examples of such problems that are of great importance in AI and algorithms. In
this paper we study, under the frameworks of random constraint satisfaction
problems and random Bayesian networks, a typical tractable subclass
characterized by the treewidth of the problems. We show that the property of
having a bounded treewidth for CSPs and Bayesian network inference problem has
a phase transition that occurs while the underlying structures of problems are
still sparse. This implies that algorithms making use of treewidth based
structural knowledge only work efficiently in a limited range of random
instance.
