The complexity of flood-filling games on graphs

We consider the complexity of problems related to the combinatorial game Free-Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. Although computing the minimum number of moves required to flood an arbitrary graph is known to be NP-hard, we demonstrate a polynomial time algorithm to compute the minimum number of moves required to link each pair of vertices. We apply this result to compute in polynomial time the minimum number of moves required to flood a path, and an additive approximation to this quantity for an arbitrary k×nk×n board, coloured with a bounded number of colours, for any fixed kk. On the other hand, we show that, for k≥3k≥3, determining the minimum number of moves required to flood a k×nk×n board coloured with at least four colours remains NP-hard.

► We study the combinatorial game Flood-It, generalised to graphs.
► The goal is to compute the number of moves required to flood the graph.
► Computing the number of moves required to link any given pair of vertices is in P.
► We compute an additive approximation for rectangular k×nk×n boards in polynomial time.
► Solving the problem exactly remains NP-hard on rectangular 3×n3×n boards.