论文标题
图表上的循环移动问题
Cyclic Shift Problems on Graphs
论文作者
论文摘要
我们研究了一个受经典机械拼图启发的新重新配置问题：在给定图的每个顶点上都放置了彩色令牌；还为我们提供了图表上的一组明显的周期。我们的任务是将令牌从给定的初始配置重新安排，通过沿杰出的循环使用循环移动操作，从给定的初始配置重新排列。我们首先研究了一大批图形，该图表概括了几个经典的难题，我们给出了可以从给定的初始配置来达到最终配置的表征。我们的证明是建设性的，并且会产生有效的方法，用于转移令牌以达到所需的配置。另一方面，当目标是找到最短的变化操作序列时，我们表明问题是NP-HARD，即使对于只有两种不同颜色的令牌的难题也是如此。
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 first investigate a large class of graphs, which generalizes several classic 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.
