  Local search is widely used to solve combinatorial optimisation problems and
to model biological evolution, but the performance of local search algorithms
on different kinds of fitness landscapes is poorly understood. Here we consider
how fitness landscapes can be represented using valued constraints, and
investigate what the structure of such representations reveals about the
complexity of local search.
  First, we show that for fitness landscapes representable by binary Boolean
valued constraints there is a minimal necessary constraint graph that can be
easily computed. Second, we consider landscapes as equivalent if they allow the
same (improving) local search moves; we show that a minimal constraint graph
still exists, but is NP-hard to compute.
  We then develop several techniques to bound the length of any sequence of
local search moves. We show that such a bound can be obtained from the
numerical values of the constraints in the representation, and show how this
bound may be tightened by considering equivalent representations. In the binary
Boolean case, we prove that a degree 2 or tree-structured constraint graph
gives a quadratic bound on the number of improving moves made by any local
search; hence, any landscape that can be represented by such a model will be
tractable for any form of local search.
  Finally, we build two families of examples to show that the conditions in our
tractability results are essential. With domain size three, even just a path of
binary constraints can model a landscape with an exponentially long sequence of
improving moves. With a treewidth-two constraint graph, even with a maximum
degree of three, binary Boolean constraints can model a landscape with an
exponentially long sequence of improving moves.
