DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.43

Reconfiguration of Labeled Matchings in Triangular Grid Graphs

Authors: Naonori Kakimura and Yuta Mishima

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

This paper introduces a new reconfiguration problem of matchings in a triangular grid graph. In this problem, we are given a nearly perfect matching in which each matching edge is labeled, and aim to transform it to a target matching by sliding edges one by one. This problem is motivated to investigate the solvability of a sliding-block puzzle called "Gourds" on a hexagonal grid board, introduced by Hamersma et al. [ISAAC 2020]. The main contribution of this paper is to prove that, if a triangular grid graph is factor-critical and has a vertex of degree 6, then any two matchings can be reconfigured to each other. Moreover, for a triangular grid graph (which may not have a degree-6 vertex), we present another sufficient condition using the local connectivity. Both of our results provide broad sufficient conditions for the solvability of the Gourds puzzle on a hexagonal grid board with holes, where Hamersma et al. left it as an open question.

Cite as

Naonori Kakimura and Yuta Mishima. Reconfiguration of Labeled Matchings in Triangular Grid Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kakimura_et_al:LIPIcs.ISAAC.2024.43,
  author =	{Kakimura, Naonori and Mishima, Yuta},
  title =	{{Reconfiguration of Labeled Matchings in Triangular Grid Graphs}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.43},
  URN =		{urn:nbn:de:0030-drops-221709},
  doi =		{10.4230/LIPIcs.ISAAC.2024.43},
  annote =	{Keywords: combinatorial reconfiguration, matching, factor-critical graphs, sliding-block puzzles}
}

Search Results

Documents authored by Mishima, Yuta

Reconfiguration of Labeled Matchings in Triangular Grid Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message