
Swapping Colored Tokens on GraphsSwapping Colored Tokens on Graphs 
"/Yamanaka, Katsuhisa/"Yamanaka, Katsuhisa ,
"/Horiyama, Takashi/"Horiyama, Takashi ,
"/Kirkpatrick, David/"Kirkpatrick, David ,
"/Otachi, Yota/"Otachi, Yota ,
"/Saitoh, Toshiki/"Saitoh, Toshiki ,
"/Uehara, Ryuhei/"Uehara, Ryuhei ,
"/Uno, Yushi/"Uno, Yushi
9214pp.619

628 , 20150805 , Springer
ISSN:03029743
ISBN:9783319218397
Description
We investigate the computational complexity of the followingproblem. We are given a graph in which each vertex has the current and target colors. Each pair of adjacent vertices can swap their current colors. Our goal is to perform as small numbers of swappings as possible so that the current and target colors agree at each vertex. When the colors are chosen from {1,2,...,c}, we call this problem cColored Token Swapping since the current color of a vertex can be seen as a colored token placed on the vertex. We show that cColored Token Swapping is NPcomplete for every constant c>3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2Colored Token Swapping can be solved in polynomial time for general graphs and in linear time for trees.
Algorithms and Data Structures, 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 57, 2015. Proceedings
FullText
https://dspace.jaist.ac.jp/dspace/bitstream/10119/13768/1/21475.pdf