Local Search on Vertex Coloring for Bipartite Graphs
2026-06-08 • Neural and Evolutionary Computing
Neural and Evolutionary Computing
AI summaryⓘ
The authors study how well local search methods work for a tricky problem called vertex coloring, which involves coloring graph nodes without conflicts. They examine bipartite graphs and find that some graph structures only allow solutions that are globally best, while others can trap local search in bad solutions. To improve results, the authors design a smarter mutation approach that favors removing less common colors and prove it quickly finds the best coloring in complete bipartite graphs. This method runs much faster than traditional random local search, highlighting benefits of using more informed search steps.
local searchvertex coloringNP-hardbipartite graphslocal optimamutation operatorgray-box optimizationcomplete bipartite graphsrandom local searchoptimization run time
Authors
Johanna Gasse
Abstract
Local search is a well-known heuristic method used in optimization. In this thesis, we explore its capabilities on the vertex coloring problem, an $NP$-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)$. 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.