Reconfiguration of labeled matchings in triangular grid graphs

Naonori Kakimura, Yuta Mishima

Introduction

This research explores the reconfiguration of labeled matchings within triangular grid graphs, a problem rooted in both combinatorial reconfiguration and recreational mathematics. Specifically, it addresses the "Gourds" sliding-block puzzle played on hexagonal boards. In this puzzle, $1 \times 2$ "dominoes" (labeled matchings) are moved across a grid. The central question is whether any configuration of these labeled edges can be transformed into any other through a sequence of "sliding" moves into an empty vertex (the "hole").

Problem Complexity: Grids with Holes

While previous studies focused on hexagonal boards without internal gaps, this paper tackles the significantly more complex case of boards containing holes. Since triangular grid graphs are the dual of hexagonal grids, solving the matching problem on the former provides a direct theoretical solution for the puzzle on the latter.

A triangular grid graph with two holes.

Methodology

The authors utilize two primary graph-theoretic frameworks to establish reconfigurability:

  1. Ear Decomposition: For factor-critical graphs—where removing any single vertex leaves a perfect matching—the authors employ ear decomposition. This involves building the graph incrementally using paths and cycles, identifying "admissible" sequences that permit piece movement without deadlocks.
  2. Hamilton Cycles and Local Connectivity: In "locally-connected" graphs (where a vertex's neighbors are themselves connected), the existence of a Hamilton cycle is leveraged. This cycle serves as a track for rotating and swapping pieces, utilizing algorithms akin to a bubble sort.

Key Insights and the Star of David Exception

A critical finding is that a graph must be factor-critical to be reconfigurable; otherwise, certain vertices could never host the "hole," locking surrounding pieces. The authors also discovered that having just one vertex of degree 6 (internal to the grid) is a sufficient condition for reconfigurability in 2-connected factor-critical grids.

Interestingly, the research identifies the "Star of David" graph as a unique exception. Despite being locally-connected, it is not factor-critical, representing a rare instance where reconfiguration is impossible.

The Star of David graph, a unique exception to reconfigurability.

Results and Future Directions

The paper establishes two major theorems:

  • Theorem 3.2: 2-connected factor-critical triangular grids with at least one degree-6 vertex are reconfigurable.
  • Theorem 4.2: Locally-connected triangular grids (excluding the Star of David) are reconfigurable in polynomial time ($O(n^3)$ operations).

While the locally-connected case is computationally efficient, the general factor-critical case currently lacks a polynomial upper bound. Future work aims to refine these bounds and extend the findings to other grid geometries or general planar graphs.

Summary updated

BibTeX
@inproceedings{kakimura2024reconfiguration,
  author = {Naonori Kakimura and Yuta Mishima},
  title = {{Reconfiguration of labeled matchings in triangular grid graphs}},
  booktitle = {ISAAC},
  year = {2024},
  doi = {10.4230/lipics.isaac.2024.43},
}
Figure