Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions

We study the performances of stochastic heuristic search algorithms on Uniquely Extendible Constraint Satisfaction Problems with random inputs. We show that, for any heuristic preserving the Poissonian nature of the underlying instance, the (heuristic-dependent) largest ratio α_a of constraints per variables for which a search algorithm is likely to find solutions is smaller than the critical ratio α_d above which solutions are clustered and highly correlated. In addition we show that the clustering ratio can be reached when the number k of variables per constraints goes to infinity by the so-called Generalized Unit Clause heuristic.