Sequentially Swapping Tokens: Further on Graph Classes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916867449290752 |
|---|---|
| author | Kiya, Hironori Okada, Yuto Ono, Hirotaka Otachi, Yota |
| author_facet | Kiya, Hironori Okada, Yuto Ono, Hirotaka Otachi, Yota |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_02835 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Sequentially Swapping Tokens: Further on Graph Classes Kiya, Hironori Okada, Yuto Ono, Hirotaka Otachi, Yota Data Structures and Algorithms 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. |
| title | Sequentially Swapping Tokens: Further on Graph Classes |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2210.02835 |