All ascents exponential from valued constraint graphs of pathwidth three

Artem Kaznatcheev, Willemijn Volgering

Many combinatorial optimization problems can be formulated as finding an assignment that maximizes some pseudo-Boolean function (that we call the fitness function). Strict local se…