Notes and Comments:
Comment: Results for special cases exist; for example, 2-opt local search for the TSP is expected to require a polynomial number of steps (to be precise: O(n^{10} log n)) to find a local minimum in the worst-case for any Euclidean TSP instance [Chandra et al., 1999]. Other work on this subject is referenced in Chandra et al. [1999].
Comment: The formalisation in Definition 4.4 is based on the assumption that the given optimisation problem is stated as a minimisation problem (as stated on p.16, this assumption is made, without loss of generality, throughout the book).
Comment: The dotted lines are exactly those edges with weight < 0.01 that are required to make the partial PCGs connected; there are other edges of weight < 0.01 between the nodes of these partial PCGs that are not shown.