The search functionality is under construction.

The search functionality is under construction.

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

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)

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Kwon Kham SAI, Giovanni VIGLIETTA, Ryuhei UEHARA, "Cyclic Shift Problems on Graphs" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 532-540, March 2022, doi: 10.1587/transinf.2021FCP0010.

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.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021FCP0010/_p

Copy

@ARTICLE{e105-d_3_532,

author={Kwon Kham SAI, Giovanni VIGLIETTA, Ryuhei UEHARA, },

journal={IEICE TRANSACTIONS on Information},

title={Cyclic Shift Problems on Graphs},

year={2022},

volume={E105-D},

number={3},

pages={532-540},

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.},

keywords={},

doi={10.1587/transinf.2021FCP0010},

ISSN={1745-1361},

month={March},}

Copy

TY - JOUR

TI - Cyclic Shift Problems on Graphs

T2 - IEICE TRANSACTIONS on Information

SP - 532

EP - 540

AU - Kwon Kham SAI

AU - Giovanni VIGLIETTA

AU - Ryuhei UEHARA

PY - 2022

DO - 10.1587/transinf.2021FCP0010

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E105-D

IS - 3

JA - IEICE TRANSACTIONS on Information

Y1 - March 2022

AB - 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.

ER -