跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2609.37118 · v2

Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable

首次提交 2026-09-29 17:28
版本更新 2026-11-18 19:03
雷达观测 2026-11-19 15:04
arXiv ↗PDF ↗

摘要

We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids Pk□PnP_k\square P_n with at most three colors. For every fixed height kk, it computes the minimum number of moves and an optimal sequence in NO(k2)N^{O(k^2)} time, where N=knN=kn. This resolves the previously open three-color case on complete 3×n3\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, and consecutive layers are joined by an edge. For a family of three-row boards, every optimal admissible painting tree has a common-ancestor chain of depth linear in the board width. For any fixed height and palette size, we give a deterministic EPTAS via a separate budget-parameterized algorithm, and we show that no FPTAS exists for k≥3k\geq 3 with at least four colors unless P = NP. We also provide a solver for 3×n3\times n boards, implemented with AI assistance based on the algorithm described in this paper. The implementation is available at GitHub

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v2,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v2 · 2026-11-18 19:03 · 最新观测版本

Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable

We give a deterministic algorithm for \textsc{Free-Flood-It} on rectangular grids Pk□PnP_k\square P_n with at most three colors. For every fixed height kk, it computes the minimum number of moves and an optimal sequence in NO(k2)N^{O(k^2)} time, where N=knN=kn. This resolves the previously open three-color case on complete 3×n3\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, and consecutive layers are joined by an edge. For a family of three-row boards, every optimal admissible painting tree has a common-ancestor chain of depth linear in the board width. For any fixed height and palette size, we give a deterministic EPTAS via a separate budget-parameterized algorithm, and we show that no FPTAS exists for k≥3k\geq 3 with at least four colors unless P = NP. We also provide a solver for 3×n3\times n boards, implemented with AI assistance based on the algorithm described in this paper. The implementation is available at GitHub

查看此版本解读 →查看此版本原文 ↗