论文标题
依次交换令牌：在图类上进一步交换
Sequentially Swapping Tokens: Further on Graph Classes
论文作者
论文摘要
我们研究了15个难题的以下变体。给定图形和两个令牌位置，我们希望找到最小长度的步行（如果存在的话），以便沿着步行的令牌交换的序列从另一个获得了一个给定的令牌位置之一。 Yamanaka等人将此问题作为顺序令牌交换引入。 [JGAA 2019]，他表明该问题通常是棘手的，但可以解决树木，完整的图和周期的多项式时间。在本文中，我们提出了用于块状图形的多项式时间算法，其中包括所有先前已知的情况。我们还提出了一般工具，以显示限制图类（例如弦图和弦琴两分图）上问题的硬度。我们还表明，在网格和国王的图上，问题很困难，这些图形是对应于15个难题及其带有轻松动作的变体的图。
We study the following variant of the 15 puzzle. Given a graph and two token placements on the vertices, we want to find a walk of the minimum length (if any exists) such that the sequence of token swappings along the walk obtains one of the given token placements from the other one. This problem was introduced as Sequential Token Swapping by Yamanaka et al. [JGAA 2019], who showed that the problem is intractable in general but polynomial-time solvable for trees, complete graphs, and cycles. In this paper, we present a polynomial-time algorithm for block-cactus graphs, which include all previously known cases. We also present general tools for showing the hardness of the problem on restricted graph classes such as chordal graphs and chordal bipartite graphs. We also show that the problem is hard on grids and king's graphs, which are the graphs corresponding to the 15 puzzle and its variant with relaxed moves.
