Cyclic Shift Problems on Graphs

• SAI Kwon Kham

  School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)

• VIGLIETTA Giovanni

  School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)

• UEHARA Ryuhei

  School of Information Science, Japan Advanced Institute of Science and Technology (JAIST)

Abstract

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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E105.D (3), 532-540, 2022-03-01

  The Institute of Electronics, Information and Communication Engineers

Keywords

• reconfiguration problem
• cyclic shift puzzle
• permutation group
• generator
• NP-hard problem

Details

• CRID: 1390573242447968000
• NII Article ID: 130008165593
• DOI: 10.1587/transinf.2021fcp0010
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E105.D/3/E105.D_2021FCP0010/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed