Elementary Landscapes: On the semi-decomposibility of select NP-Hard Optimization Problems

Several NP-Hard combinatorial optimization problems have "elementary landscapes." This means that a matrix describing common "natural" neighborhood structures has eigenvectors and eigenvalues that can be used to compute a number of surprising properties about the resulting local search landscape. This includes computing the average value over the entire search space, as well as the average value of the neighbors of every point in the search space. It also places bounds on objective function values for local minima and local maxima. The Traveling Salesman Problem, Graph Coloring and Min-Cut Graph Partitioning all have elementary landscapes. We extend the analysis of elementary landscapes in two directions. First, we have developed a new model of specific elementary landscapes that makes it possible to compute certain properties of elementary landscapes over partial neighborhoods. Second, we show that other NP-Hard problems such as MAX-K-SAT are a superposition of a small number of elementary landscapes. A Walsh-Hadamard Transform is used to create a polynomial representation of the evaluation function. For MAX-K-SAT the resulting polynomial is of order K and each set of coefficients of a specific order form an elementary landscape. Thus, MAX-3-SAT, the most commonly used objective function for MAXSAT problems, is a superposition of exactly 3 elementary landscapes, making it possible to quickly compute some of the basic properties associated with elementary landscapes.