Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four
<|reference_start|>Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth Four: We examine the complexity of maximising fitness via local search on valued constraint satisfaction problems (VCSPs). We consider two kinds of local ascents: (1) steepest ascents, where each step changes the domain that produces a maximal increase in fitness; and (2) $\prec$-ordered ascents, where -- of the domains with available fitness increasing changes -- each step changes the $\prec$-minimal domain. We provide a general padding argument to simulate any ordered ascent by a steepest ascent. We construct a VCSP that is a path of binary constraints between alternating 2-state and 3-state domains with exponentially long ordered ascents. We apply our padding argument to this VCSP to obtain a Boolean VCSP that has a constraint (hyper)graph of arity 5 and pathwidth 4 with exponential steepest ascents. This is an improvement on the previous best known construction for long steepest ascents, which had arity 8 and pathwidth 7.<|reference_end|>
@article{kaznatcheev2024exponential,
    title={Exponential Steepest Ascent from Valued Constraint Graphs of Pathwidth
  Four},
    author={Artem Kaznatcheev and Melle van Marle},
    journal={arXiv preprint arXiv:2405.12906},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.12906},
    primaryClass={cs.DM cs.DS q-bio.PE}
}