cs.NE · 2606.07361 Copy arXiv ID · Jun 5, 2026 Save Combinatorial Landscape Analysis for Dominating Set and Vertex Coloring Authors: Johanna Gasse , Antonia Heinen , Felix Knöfel , Timo Kötzing , Maxim Stanko
Organizations: Hasso Plattner Institute, Potsdam, Germany
Abstract 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).
Explore similar work Jun 6, 2026 · Johanna Gasse, Antonia Heinen, Hendrik Higl +1 Black-Box Optimization Combinatorial Optimization
Aug 4, 2026 · Shoichiro Tanaka, Keiki Takadama, Hiroyuki Sato Multi-Objective Optimization Optimization Landscape
Jun 8, 2026 · cs.NE J/K move · Enter open · S save
Johanna Gasse
Fachgebiet Algorithm Engineering der Digital-Engineering-Fakultät der Universität Potsdam
Local search is a well-known heuristic method used in optimization. In this thesis, we explore its capabilities on the vertex coloring problem, an
N P NP N P -hard problem with relevance in both theoretical analysis and practical application. To recognize limitations in the applicability of local search of the vertex coloring problem, we analyze local search landscapes on differently-structured bipartite graphs. We identify structures that ensure only global optima can exist as well as ones that enable the existence of non-global local optima, showing that on general bipartite graphs, it is possible for local search to return arbitrarily bad results. Further, we analyze the capabilities of local search on graphs where a local optimum can be found. To do so, we introduce a gray-box local search mutation operator that removes less frequent colors with higher probability and prove that it finds an optimal coloring on complete bipartite graphs in an expected run time of
Θ ( n log n ) Θ(n \log n) Θ ( n log n ) . This is a drastic improvement to the exponential tun time of the black-box Random Local Search, showing that gray-box mutation operators can improve the run time of local search.