arXiv preprint ·
Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Sample Complexity of Equivariant Reinforcement Learning
A Separation Between Types of Quantum Oracle Separations
Degree Balance as a Fine-Grained Complexity Boundary for Quantum SAT
Experimentally Testable Quantum Advantage in Shallow Circuits
The Commuting Local Hamiltonian Problem: Relativized Evidence Against BQP-Hardness
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.