The Complexity of Flood Filling Games by Clifford, Jalsenius, Monanaro, Sach Shows for the actualy grid version:
(1) c GE 3 then flood-it and free-flood-it are NP-hard,
(2) 3xn, unbounded numb of colors, flood-it and free-flood-it are NP-hard,
(3) 2xn, ubded colors, flood-it is in P (OPEN in this paper: free-flood-it)
(4) c=2 then free-flood-it is in P,
(5) there is a (c-1)-approx and a randomized 2c/3-approx.
(6) no constant-approx.
(7) Number of moves needed in the worst case is Omega(sqrt(c)n)
(8) For a random board, cge 2, requires Omega(n).
2-Free-Flood-it is polynomial by Lagoutte
For free-flood-it on graphs, c=2, in Poly time.
The Complexity of Free-Flood-It on 2xn boards by Meek and Scott
When restricted to 2xn, free-flood-it FPT with c as parameter.
An Algorithmic analysis of flood-it and free-flood-it on graph powers by Souza, Protti, Silva
Flood-it on AT-free graphs by Hon, Kloks, Liu, Liu, Wang
How bad is the freedom to flood-it? by Belmonte, Ghadikolaei, Kiyomi, Lampis, Otachi
Extremal properties of flood-filling games by Meeks and Vu
Looks at which graphs give the worst number of moves needed.
Parameterized complexity of flood-filling games on trees by Souza, Protti, da Silva
(1) Flood-it is NP-hard even on trees where all leaves are LE 2 from root.
(2) Flood-it is equiv to Restricted Shortest Common Subsequence.
Tractability and hardness of flood filling games on trees by Fellows, Souza, Protti,da Silva
(1) Flood-it is equiv to Restricted Shortest Common Subsequence.
(2) 3-color tree versions of flood-it and free-flood-it are NP-hard.
A Survey on the Complexity of Flood-Filling Games by Fellows, Protti, Rosamond, da Silva, Souza
The Complexity of Some Problems on Subsequences and Supersequences by Maier
The Shortest Common Supersequence Problem over a binary alphabet is NPC by Raiha and Ukkonen]