Swapping Colored Tokens on Graphs

DOI10.1007/978-3-319-21840-3_51MaRDI QIDQ3449858zbMATH OpenOpenAlexFDO

Authors Katsuhisa Yamanaka, Takashi Horiyama, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno, David Kirkpatrick

Publication date 30 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.06816

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 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 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.

Recommendations

• Swapping colored tokens on graphs
• Sequentially swapping colored tokens on graphs
• Sequentially swapping colored tokens on graphs
• Swapping labeled tokens on graphs
• Sequentially swapping tokens: further on graph classes
• Token shifting on graphs
• Online coloring a token graph
• Recoloring graphs via tree decompositions
• Token Swapping on Trees

Cites work

• Combinatorial optimization. Theory and algorithms
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1033192 (Why is no real title available?)
• Planar 3DM is NP-complete
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees
• Swapping labeled tokens on graphs
• The complexity of finding minimum-length generator sequences

Cited in

(13)

• Swapping colored tokens on graphs
• Introduction to reconfiguration
• Swapping labeled tokens on graphs
• Sorting on graphs by adjacent swaps using permutation groups
• Token shifting on graphs
• Sequentially swapping colored tokens on graphs
• The time complexity of the token swapping problem and its parallel variants
• Sequentially swapping colored tokens on graphs
• The time complexity of permutation routing via matching, token swapping and a variant
• Complexity of token swapping and its variants
• Token Swapping on Trees
• Polynomial time algorithms for the token swapping problem on cographs
• Complexity of token swapping and its variants

This page was built for publication: Swapping Colored Tokens on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449858)