2026-07-22T03:56:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11896 2024-03-06T10:48:57Z ddc:004 open_access

Shortest Reconfiguration of Colorings Under Kempe Changes Bonamy, Marthe Heinrich, Marc Ito, Takehiro Kobayashi, Yusuke Mizuta, Haruka Mühlenthaler, Moritz Suzuki, Akira Wasa, Kunihiro Combinatorial Reconfiguration Graph Algorithms Graph Coloring Kempe Equivalence A k-coloring of a graph maps each vertex of the graph to a color in {1, 2, …, k}, such that no two adjacent vertices receive the same color. Given a k-coloring of a graph, a Kempe change produces a new k-coloring by swapping the colors in a bicolored connected component. We investigate the complexity of finding the smallest number of Kempe changes needed to transform a given k-coloring into another given k-coloring. We show that this problem admits a polynomial-time dynamic programming algorithm on path graphs, which turns out to be highly non-trivial. Furthermore, the problem is NP-hard even on star graphs and we show that on such graphs it admits a constant-factor approximation algorithm and is fixed-parameter tractable when parameterized by the number k of colors. The hardness result as well as the algorithmic results are based on the notion of a canonical transformation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marthe Bonamy and Marc Heinrich and Takehiro Ito and Yusuke Kobayashi and Haruka Mizuta and Moritz Mühlenthaler and Akira Suzuki and Kunihiro Wasa 2020 Is Part Of LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2020.35 urn:nbn:de:0030-drops-118961 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.35 eng https://creativecommons.org/licenses/by/3.0/legalcode