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 7), there are fitness landscapes for which an exponential number of steps may be required to reach a local optimum.