Elementary Landscape Decomposition of the Hamiltonian Path Optimization Problem

Abstract

There exist local search landscapes where the evaluation function is an eigenfunction of the graph Laplacian that corresponds to the neighborhood structure of the search space. Problems that dis- play this structure are called “Elementary Landscapes” and they have a number of special mathematical properties. The problems that are not elementary landscapes can be decomposed in a sum of elementary ones. This sum is called the elementary landscape decomposition of the problem. In this paper, we provide the elementary landscape decomposi- tion for the Hamiltonian Path Optimization Problem under two different neighborhoods.