Sequentially Swapping Tokens: Further on Graph Classes

Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish
Title of host publicationSOFSEM 2023
Subtitle of host publicationTheory and Practice of Computer Science - 48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023, Proceedings
EditorsLeszek Gasieniec
PublisherSpringer Science and Business Media Deutschland GmbH
Pages222-235
Number of pages14
ISBN (Print)9783031231001
DOIs
Publication statusPublished - 2023
Event48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023 - Nový Smokovec, Slovakia
Duration: Jan 15 2023Jan 18 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13878 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference48th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2023
Country/TerritorySlovakia
CityNový Smokovec
Period1/15/231/18/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Sequentially Swapping Tokens: Further on Graph Classes'. Together they form a unique fingerprint.

Cite this