IEICE TRANSACTIONS on Information
Cyclic Shift Problems on Graphs
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
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
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 -
English
