Before revision:  We show that even when all variables have domains of size two and the underlying constraint graph (graph of variable interactions ) has bounded treewidth (in our construction, treewidth is 7), there are fitness landscapes for which an exponential number of steps may be required to reach a local optimum.
After revision:  We show that even when all variables have domains of size two and the underlying constraint graph (graph of variable interactions has bounded treewidth (in our construction, treewidth is 7), there are fitness landscapes for which an exponential number of steps may be required to reach a local optimum.