The search functionality is under construction.
The search functionality is under construction.

Cyclic Shift Problems on Graphs

Kwon Kham SAI, Giovanni VIGLIETTA, Ryuhei UEHARA

  • Full Text Views

    0

  • Cite this

Summary :

We study a new reconfiguration problem inspired by classic mechanical puzzles: a colored token is placed on each vertex of a given graph; we are also given a set of distinguished cycles on the graph. We are tasked with rearranging the tokens from a given initial configuration to a final one by using cyclic shift operations along the distinguished cycles. We call this a cyclic shift puzzle. We first investigate a large class of graphs, which generalizes several classic cyclic shift puzzles, and we give a characterization of which final configurations can be reached from a given initial configuration. Our proofs are constructive, and yield efficient methods for shifting tokens to reach the desired configurations. On the other hand, when the goal is to find a shortest sequence of shifting operations, we show that the problem is NP-hard, even for puzzles with tokens of only two different colors.

Publication
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.532-540
Publication Date
2022/03/01
Publicized
2021/10/08
Online ISSN
1745-1361
DOI
10.1587/transinf.2021FCP0010
Type of Manuscript
Special Section PAPER (Special Section on Foundations of Computer Science - New Trends of Theory of Computation and Algorithm -)
Category

Authors

Kwon Kham SAI
  Japan Advanced Institute of Science and Technology (JAIST)
Giovanni VIGLIETTA
  Japan Advanced Institute of Science and Technology (JAIST)
Ryuhei UEHARA
  Japan Advanced Institute of Science and Technology (JAIST)

Keyword