http://swrc.ontoware.org/ontology#TechnicalReport
Computational Complexity of Colored Token Swapping Problem
en
Iwate University
Saitama University
University of British Columbia
Japan Advanced Institute of Science and Technology
Kobe University
Japan Advanced Institute of Science and Technology
Osaka Prefecture University
Katsuhisa Yamanaka
Takashi Horiyama
David Kirkpatrick
Yota Otachi
Toshiki Saitoh
Ryuhei Uehara
Yushi Uno
We investigate the computational complexity of the following problem. 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 the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2, ... , c}, we call this problem c-Colored Token Swapping since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-Colored Token Swapping is NP-complete for every constant c ≧ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-Colored Token Swapping can be solved in polynomial time for general graphs.
We investigate the computational complexity of the following problem. 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 the minimum number of swaps so that the current and target colors agree at each vertex. When the colors are chosen from {1, 2, ... , c}, we call this problem c-Colored Token Swapping since the current color of a vertex can be seen as a colored token placed on the vertex. We show that c-Colored Token Swapping is NP-complete for every constant c ≧ 3 even if input graphs are restricted to connected planar bipartite graphs of maximum degree 3. We then show that 2-Colored Token Swapping can be solved in polynomial time for general graphs.
AN1009593X
研究報告アルゴリズム（AL）
2016-AL-156
2
1-4
2016-01-14
2188-8566