Phase Transitions and Complexity of Weighted Satisfiability and Other Intractable Parameterized Problems

Abstract

The study of random instances of NP complete and coNP complete problems has had much impact on our understand-ing of the nature of hard problems. In this work, we initiate an effort to extend this line of research to random instances of intractable parameterized problems. We propose random models for a representative intractable parameterized problem, the weighted d-CNF satisfiability, and its generalization to the constraint satisfaction problem. The exact threshold for the phase transition of the proposed models is determined. Lower bounds on the time complex-ity of variants of the DPLL algorithm for these parameter-ized problems are also established. In particularly, we show that random instances of the weighted 2-CNF satisfiability, already an intractable parameterized problem, are typically easy in both of the satisfiable and unsatisfiable regions by exploiting an interesting connection between the unsatisfia-bility of a weighted 2-CNF formula and the existence of a Hamiltonian-cycle-like global structure. 1.