2026-08-17T23:40:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22170 2024-12-04T06:53:44Z ddc:004 open_access

Reconfiguration of Labeled Matchings in Triangular Grid Graphs Kakimura, Naonori Mishima, Yuta combinatorial reconfiguration matching factor-critical graphs sliding-block puzzles 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Naonori Kakimura and Yuta Mishima 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.43 urn:nbn:de:0030-drops-221709 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.43 eng https://creativecommons.org/licenses/by/4.0/legalcode