Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable".
Paper summary: Tom: So we were talking about how they solved that fixed height case, and I want to recap the main idea here. The paper "Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable" gives a deterministic algorithm for Free-Flood-It on rectangular grids with at most three colors.
Jane: That’s right, Tom, so the thesis is that for any fixed height k, you can compute the minimum number of moves and an optimal sequence in N O(k squared) time. And it resolves the previously open case on complete three by n boards.
Lu: The proof relies on framing flooding strategies as paintings by connected regions, showing that an optimal painting forms a rooted tree with strong restrictions on colors along ancestral paths.
Meng: So instead of looking at the whole board at once, they are using this idea of a painting tree to constrain the search space into something manageable for fixed height k.
Lalam: They construct an admissible painting tree where local descriptions of that painting tree admit only polynomially many descriptions when restricted to any fixed-size connected window.
Tom: That sounds like the key mechanism, and it means that even though the board gets wide, the complexity is controlled by how high it is. It’s not just about brute force anymore, right?
Jane: Precisely. They deal with a potential issue where common ancestors form an arbitrarily long chain, but they handle that by retaining the chain on a stack and using a finite context-free recurrence to minimize the total painting cost without enumerating all possible stack contents.
Lalam: And they ensure that connectivity information at the boundary allows these local descriptions to assemble into one valid global painting. Plus, it applies to graphs supplied with an ordering into connected layers of bounded size, provided every edge lies within one layer or joins consecutive layers.
Conclusion: Tom: Looking at the full picture, the paper "Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial Time Solvable" is about taking a known hard problem on complete three by n boards and making it solvable in polynomial time when you fix the height.
Jane: It’s about proving that this specific structure allows for an efficient solution because of how the optimal painting tree behaves, especially with respect to those color restrictions along ancestral paths.
Lu: The implication is that for problems modeled this way, if you can restrict one dimension—like the height in a grid—you can gain polynomial time efficiency over what was previously exponential.
Meng: For us at scale, it means if we can find a structural property that limits the complexity related to height or depth, we might be able to tame these combinatorial games on much larger inputs than we currently could.
Lalam: So essentially, they showed that by using a structured representation like the painting tree and handling the common ancestor chain smartly with a recurrence, you can compute the exact minimum moves efficiently.
Tom: Exactly. It's not just about finding an approximation anymore; it’s about getting the exact answer in time that scales well with the fixed height. It changes how we approach these optimization problems on structured grids.
Key Laboratory of System Software Chinese Academy of Sciences · University of Chinese Academy of Sciences
cs.CC, cs.DS
Submitted: 2026-09-29
Updated: 2026-11-18
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 90/100
The gist: Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable We give a deterministic algorithm for Free-Flood-It on rectangular grids Pk□Pn with at most three colors For every fixed…
Key concepts
- Free-Flood-It
- This is a combinatorial game played on a colored graph where the goal is to make the entire graph monochromatic in the fewest moves possible. A move involves changing the color of one maximal connected component in the current coloring.
- Painting by Connected Strokes
- The problem is equivalent to finding an optimal way to paint regions on a grid. The authors use this equivalence, showing that optimizing these painting plans directly yields an optimal flooding sequence for the game.
- Admissible Painting Tree
- This is a rooted tree structure used by the algorithm. It maps the coloring strategy onto a tree where local descriptions are restricted, allowing the algorithm to efficiently manage and compute costs related to painting regions.
Terminology
Summary
Three-Color Free-Flood-It on Fixed-Height Grids Is Polynomial-Time Solvable We give a deterministic algorithm for Free-Flood-It on rectangular grids Pk□Pn 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 × n boards
Problem Formulation and Equivalence
Free-Flood-It is a one-player combinatorial game on a vertex-colored graph where a move changes the color of one maximal monochromatic connected component, aiming to make the graph monochromatic in as few moves as possible The authors establish an equivalence between flooding and painting by connected strokes, stating that p(G, f) = F(G, f) + 1 This relation allows the optimization of painting plans to yield an optimal flooding sequence The problem is framed using a representation of flooding strategies as paintings by connected regions, showing that an optimal painting can be chosen such that its regions form a rooted tree with strong restrictions on the colors along ancestral paths
Algorithmic Construction via Painting Trees
The algorithm constructs an admissible painting tree, which is a rooted tree T with color c(x) at each node and an owner map π: V (G) → V (T) The construction relies on local descriptions of a painting tree that admit only polynomially many descriptions when restricted to any fixed-size connected window Connectivity information at a column boundary is recorded by a partition ρ, and the algorithm maintains an invariant ensuring that an unfinished region cannot lose a component in this way This leads to the definition of local templates, which are rooted colored trees K and owners πB: B → V (K)
Complexity Analysis and Running Time
The running time for a fixed height k is N O(k 2), where N = kn The complexity is XP parameterized by height, as the algorithm scans columns and enumerates local descriptions of a normalized painting tree For general fixed height k and palette size c, a deterministic EPTAS is provided with running time Ok,c k N O(k 2)N The randomized approximation scheme has a running time of Ok,c k N O(k 2)N log(2/δ)
Approximation Schemes and Budget Bounds
The paper provides deterministic and randomized approximation schemes for any fixed palette size c Theorem 3 gives a deterministic EPTAS with running time Ok,c k N O(k 2)N Theorem 4 provides a randomized approximation scheme with running time Ok,c k N O(k 2)N log(2/δ) The budget-parameterized algorithm has a running time of O(N poly(b + 1, k, c)) h c squared k+3 Bell(k + 1)ib
Generalization to Graphs with Connected Layers
The results extend to graphs supplied with an ordering into connected layers of bounded size, provided every edge lies within one layer or joins consecutive layers Corollary 20 shows that for a coloring with at most three colors, the minimum number of free flooding moves and an optimal sequence can be computed in deterministic N O(h 2) time This applies to a rectangular strip with some horizontal edges deleted, provided that all vertical edges remain and every consecutive pair of columns retains at least one edge between them
Conclusion on the Method
The algorithm successfully computes the minimum cost by summarizing finite runs between stack boundaries instead of enumerating all possible stacks The final computation yields an exact deterministic algorithm for every fixed height, resolving the previously open three-color case on complete 3×n boards The method demonstrates that the common ancestor chain can be handled by a finite context-free recurrence to minimize total painting cost without enumerating all possible stack contents The final reconstruction procedure takes O(N 2) time after extracting the accepting run The algorithm is one deterministic construction taking k as input, with an exponent depending on k; it is an XP algorithm in height The proof rests on a distinction between two parts of a painting tree
Open Questions
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Deterministic algorithm for Free-Flood-It on complete k x n boards with at most three colors 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 x n boards and extends to every fixed height k, yielding an XP algorithm parameterized by height.
-
The system can compute a legal flooding sequence for any fixed palette size c and height k in deterministic time Ok(N 6 + 2Ok(c)(1/epsilon)N), which is a deterministic EPTAS for every fixed k and c.
-
A randomized approximation scheme exists that returns a legal flooding sequence whose length is at most (1 + epsilon)m(B) with probability at least 1 - delta, with running time Ok(N 6 + 2Ok(c)(1/epsilon)N log(2/delta)).
-
The system can determine the exact minimum number of moves p(G, f) by computing a finite-run cost d using a weighted pushdown system, and then recovering the optimal painting tree and reversing nonroot strokes to obtain a flooding sequence of length d - 1.
-
For graphs supplied with connected layers of bounded size h, where every edge lies within one layer or joins consecutive layers, the minimum number of free flooding moves can be computed in deterministic N O(h 2) time.
Sources
Related papers
- The Proof Analysis Problem for Constant-Depth Frege
- Hardness of Counting Orderings: Taking Gadget Amplification to the Limit
- Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and Treewidth
- Parameterized Hardness of Zonotope Containment and Neural Network Verification
- From Block Orthogonality to Decidability in Complex-Weighted Counting CSP
- Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?