The Freuder Width in a General Model of Constraint Satisfaction Problem
Jing Shen, Mei Dan · 2016
The Freuder width plays an important role for studying backtrack-free search. In this paper, we study a general random model of constraint satisfaction problem, named d-k-CSP, which exhibits exact satisfiability phase transition. We prove that the Freuder width of the model d-k-CSP is asymptotically equal to average degree.