Steepest ascent can be exponential in bounded treewidth problems
This reveals fundamental limitations in local search algorithms for combinatorial optimization, impacting researchers in AI and theoretical computer science, and is incremental as it builds on prior work with a tighter bound.
The paper tackled the complexity of local search via steepest ascent, showing that even with binary variables and bounded treewidth (7), exponential steps may be needed to reach a local optimum, improving prior constructions that required unbounded treewidth.
We investigate the complexity of local search based on steepest ascent. We show that even when all variables have domains of size two and the underlying constraint 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. This is an improvement on prior recursive constructions of long steepest ascents, which we prove to need constraint graphs of unbounded treewidth.