  Local Search is one of the fundamental approaches to combinatorial
optimization and it is used throughout AI. Several local search algorithms are
based on searching the k-exchange neighborhood. This is the set of solutions
that can be obtained from the current solution by exchanging at most k
elements. As a rule of thumb, the larger k is, the better are the chances of
finding an improved solution. However, for inputs of size n, a na\"ive
brute-force search of the k-exchange neighborhood requires n to the power of
O(k) time, which is not practical even for very small values of k.
  Fellows et al. (IJCAI 2009) studied whether this brute-force search is
avoidable and gave positive and negative answers for several combinatorial
problems. They used the notion of local search in a strict sense. That is, an
improved solution needs to be found in the k-exchange neighborhood even if a
global optimum can be found efficiently.
  In this paper we consider a natural relaxation of local search, called
permissive local search (Marx and Schlotter, IWPEC 2009) and investigate
whether it enhances the domain of tractable inputs. We exemplify this approach
on a fundamental combinatorial problem, Vertex Cover. More precisely, we show
that for a class of inputs, finding an optimum is hard, strict local search is
hard, but permissive local search is tractable.
  We carry out this investigation in the framework of parameterized complexity.
