文章基本信息

标题：Shortest Reconfiguration of Colorings Under Kempe Changes
本地全文：下载
作者：Marthe Bonamy ; Marc Heinrich ; Takehiro Ito 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：154
页码：35:1-35:14
DOI：10.4230/LIPIcs.STACS.2020.35
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Combinatorial Reconfiguration; Graph Algorithms; Graph Coloring; Kempe Equivalence