Metraipolis › archive › dc_c41fed569cf7

Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable — arXiv:2609.37118

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.37118
License (as archived)
CC0-1.0
Archived
2026-10-07T19:19:04.108Z
SHA-256 of the archived text
8b554b7908461a67b0c7cdce59bccb5f610907c1e3cf515320747d872988b737
Stable URL of this page
https://metraipolis.com/documento/dc_c41fed569cf7

How to cite

Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable — arXiv:2609.37118 — arXiv (en), https://arxiv.org/abs/2609.37118 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c41fed569cf7 (Metraipolis archive dc_c41fed569cf7, sha256 8b554b7908461a67b0c7cdce59bccb5f610907c1e3cf515320747d872988b737)
BibTeX
@misc{dcc41fed569cf7,
  title = {Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable — arXiv:2609.37118},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.37118},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c41fed569cf7; sha256 8b554b7908461a67b0c7cdce59bccb5f610907c1e3cf515320747d872988b737},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37118. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids $P_k\square P_n$ with at most three colors. For every fixed height $k$, it computes the minimum number of moves and an optimal sequence in $N^{O(k^2)}$ time, where $N=kn$. This resolves the previously open three-color case on complete $3\times n$ boards. The proof uses a representation of flooding strategies as paintings by connected regions. We show that an optimal painting can be chosen so that its regions form a rooted tree with strong restrictions on the colors along ancestral paths. These restrictions make the part of the tree visible in any fixed-size connected window admit only polynomially many descriptions. The remaining common ancestors may form an arbitrarily long chain. We retain that chain on a stack and use a finite context-free recurrence to minimize the total painting cost without enumerating all possible stack contents. Connectivity information at the boundary ensures that the resulting local descriptions assemble into one valid global painting. The argument also applies to graphs supplied with an ordering into connected layers of bounded size, provided every edge lies within one layer or joins consecutive layers. A family of three-row boards shows that the unbounded ancestor chains handled by the algorithm are necessary even for optimal paintings. For any fixed height and palette size, we also give a deterministic EPTAS and a randomized sampling variant with an explicit failure-probability bound. These approximation results use a separate algorithm with single-exponential dependence on the move budget.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in cs.DS).
Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.37118 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T18:45:07.104Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).