Preenchendo lacunas para a solução polinomial do Jogo da Inundação em grafos de co-comparabilidade

Abstract

The Flood-it Game is a game played on a board (an 𝑚 × 𝑛 matrix) where each cell has a color from a given set of colors. The goal is to make all cells have the same color with the minimum number of moves. The graphs that model the Flood-it Game board are called grid graphs. A graph that allows a transitive orientation for its edges is a comparability graph. A graph is a co-comparability graph if and only if its complement is a comparability graph. Fleischer and Woeginger (2012) claim that the Flood-it Game can be efficiently solved on co-comparability graphs. However, this result was refuted by Lorenzi and Almeida (2021), who showed a counterexample where the algorithm does not finish. In this project, we filled some gaps in Fleischer and Woeginger’s (2012) solution by providing algorithms to address them. Specifically, we explore the solution provided by Fleischer and Woeginger (2012) for the Flood-it Game, considering it for co-comparability graphs with minimal or maximal pivot.