2024/05/21 by Artem Kaznatcheev, Kaznatcheev, Artem, Melle van Marle +1 · 2 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #Optimization and Packing Problems #Populations and Evolution (q-bio.PE) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2405.12906
openalex publication_date 2024/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.