Combinatorial Landscape Analysis for Dominating Set and Vertex Coloring
This work provides theoretical insights into the structure of local optima for two classic NP-hard problems, which is relevant for understanding the difficulty of heuristic search.
The paper analyzes the combinatorial landscapes of Dominating Set and Vertex Coloring problems, classifying them as unimodal, plateau-unimodal, equimodal, or multimodal for various graph classes and two neighborhood operators.
We analyze the two combinatorial problems of Dominating Set and Vertex Coloring regarding what kind of local optima are present for various instances. For a variety of graph classes each, we determine whether the induced landscapes are unimodal, plateau-unimodal (all optima are just one plateau), equimodal (all local optima are global) or truly multimodal. We do this for two different neighborhood operators, one based on making only a single change and one also allowing swaps (interchanging two parts of the solution).