Swapping Colored Tokens on Graphs

DOI 機関リポジトリ Web Site Web Site 被引用文献3件 参考文献16件

説明

We investigate the computational complexity of the following problem. We are given a graph in which each vertex has an initial and a target color. 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 targetcolors 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 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 and in linear time for trees. Besides, we show that, the problem for complete graphs is fixed-parameter tractable when parameterized by the number of colors, while it is known to be NP-complete when the number of colors is unbounded.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/16224

収録刊行物

被引用文献 (3)*注記

もっと見る

参考文献 (16)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ