Phase Transition of Tractability in Constraint Satisfaction and Bayesian Network Inference
This work addresses the challenge of identifying tractable subclasses for NP-complete problems in AI, but it is incremental as it builds on known treewidth frameworks.
The paper investigates the tractability of constraint satisfaction problems and Bayesian network inference by analyzing the phase transition of bounded treewidth in random instances, showing that treewidth-based algorithms are efficient only within a limited range of sparse structures.
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.