Sequentially swapping tokens: further on graph classes

DOI10.1007/978-3-031-23101-8_15MaRDI QIDQ6169527zbMATH OpenOpenAlexFDO

Authors Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

Publication date 14 August 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2210.02835

zbMATH Keywords

(generalized) 15 puzzleblock-cactus graphgrid graphKing's graphsequential token swapping

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Abstract: 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.

Recommendations

• Sequentially swapping colored tokens on graphs
• Sequentially swapping colored tokens on graphs
• Swapping labeled tokens on graphs
• Complexity of token swapping and its variants
• Complexity of token swapping and its variants

Cites work

• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• Fast Pattern Matching in Strings
• Graph theory
• Hamilton Paths in Grid Graphs
• HAMILTONian circuits in chordal bipartite graphs
• Introduction to reconfiguration
• Sequentially swapping colored tokens on graphs
• Steiner trees, connected domination and strongly chordal graphs
• The \((n^ 2-1)\)-puzzle and related relocation problems
• The complexity of change
• The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs
• The Rectilinear Steiner Tree Problem is NP-Complete

Cited in

(3)

• Swapping labeled tokens on graphs
• Swapping Colored Tokens on Graphs
• Complexity of action path finding with small precondition sets

This page was built for publication: Sequentially swapping tokens: further on graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6169527)