New landscape analysis maps local optima for Dominating Set and Vertex Coloring

Researchers Johanna Gasse, Antonia Heinen, Felix Knöfel, Timo Kötzing, and Maxim Stanko analyzed the local optima structure of two classic NP-hard problems: Dominating Set and Vertex Coloring. For each problem, they examined multiple graph classes (e.g., trees, bipartite, or random graphs) and classified the resulting fitness landscapes into four types: unimodal (a single optimum), plateau-unimodal (all optima on one connected plateau), equimodal (every local optimum is also global), or truly multimodal (multiple distinct local optima).

The study uses two different neighborhood operators: a standard single-change operator (flip one vertex) and a swap operator that exchanges two parts of the solution. This distinction matters for evolutionary algorithms, as operators determine how easily a search can escape local optima. The results provide a map of which graph classes are easy (unimodal) vs. hard (truly multimodal) for these problems. For example, some classes permit plateau-unimodal landscapes where hill climbing can still find a global optimum despite plateaus.