Flood It Game. The problem is to find the optimal sequence of movies. Is this equiv to just finding the optimal number of moves?

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]