TY - GEN
T1 - Shortest reconfiguration of colorings under kempe changes
AU - Bonamy, Marthe
AU - Ito, Takehiro
AU - Mizuta, Haruka
AU - Suzuki, Akira
AU - Heinrich, Marc
AU - Kobayashi, Yusuke
AU - Mühlenthaler, Moritz
AU - Wasa, Kunihiro
N1 - Funding Information:
Acknowledgements This work is partially supported by JSPS and MEAE-MESRI under the Japan-France Integrated Action Program (SAKURA).
Funding Information:
Funding Takehiro Ito: Partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP18H04091 and JP19K11814, Japan. Yusuke Kobayashi: Supported by JST ACT-I Grant Number JPMJPR17UB, and JSPS KAKENHI Grant Numbers JP16K16010 and JP18H05291, Japan. Akira Suzuki: Partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAK-ENHI Grant Numbers JP17K12636 and JP18H04091, Japan. Kunihiro Wasa: Partially supported by JST CREST Grant Numbers JPMJCR18K3 and JP-MJCR1401, and JSPS KAKENHI Grant Number 19K20350, Japan.
Publisher Copyright:
© Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa; licensed under Creative Commons License CC-BY
PY - 2020/3
Y1 - 2020/3
N2 - 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.
AB - 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.
KW - Combinatorial Reconfiguration
KW - Graph Algorithms
KW - Graph Coloring
KW - Kempe Equivalence
UR - http://www.scopus.com/inward/record.url?scp=85082122425&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85082122425&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2020.35
DO - 10.4230/LIPIcs.STACS.2020.35
M3 - Conference contribution
AN - SCOPUS:85082122425
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
A2 - Paul, Christophe
A2 - Blaser, Markus
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020
Y2 - 10 March 2020 through 13 March 2020
ER -