[Paper] Combinatorial Landscape Analysis for Dominating Set and Vertex Coloring

Source: arXiv - 2606.07361v1

Overview

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).

Key Contributions

This paper presents research in the following areas:

• cs.NE
• cs.DM

Methodology

Please refer to the full paper for detailed methodology.

Practical Implications

This research contributes to the advancement of cs.NE.

Authors

• Johanna Gasse
• Antonia Heinen
• Felix Knöfel
• Timo Kötzing
• Maxim Stanko

Paper Information

• arXiv ID: 2606.07361v1
• Categories: cs.NE, cs.DM
• Published: June 5, 2026
• PDF: Download PDF