An algorithmic analysis of Flood-it and Free-Flood-it on graph powers
Uéverton S. Souza, Fábio Protti, Maise Dantas da Silva
Abstract
Flood-it is a combinatorial game played on a colored graph
G whose aim is to make the graph monochromatic using the
minimum number of flooding moves, relatively to a fixed
pivot. Free-Flood-it is a variant where the pivot can be freely chosen
for each move of the game. The standard versions of Flood-it and
Free-Flood-it are played on m ×n grids. In this
paper we analyze the behavior of these games when played on other
classes of graphs, such as d-boards, powers of cycles and
circular grids. We describe polynomial time algorithms to play
Flood-it on C2n (the second power
of a cycle on n vertices), 2 ×n
circular grids, and some types of d-boards (grids with a
monochromatic column). We also show that Free-Flood-it is NP-hard on
C2n and 2 ×n
circular grids.
Full Text: PDF PostScript