O problema da inundação em grafos de co-comparabilidade

Abstract

The Flood-It Problem consists of determining a minimum sequence of moves capable of transforming an initially colored graph into a monochromatic one. Despite its simple and game-oriented formulation, the problem presents significant computational complexity, being NP-hard for several graph classes. Among the existing results in the literature, Fleischer e Woeginger (2012) proposed a polynomial-time algorithm for the fixed-pivot Flood-It Problem on co-comparability graphs, a result that remained widely cited for more than a decade. However, Lorenzi and Almeida (2022) demonstrated the existence of a termination flaw in the recursive formulation employed by the algorithm, reopening the problem for this graph class. In this work, we investigate the structural limitations of the original approach and identify, in addition to the previously known cyclic dependency issue, cases of pivot inaccessibility and overestimation of the total flooding cost. As the main contribution, we propose an iterative adaptation based on shortest-path techniques and successive state relaxation, inspired by the Floyd-Warshall algorithm. The new formulation replaces the recursive dependency with an iterative process capable of guaranteeing convergence and correctness even in the presence of dependency cycles. Furthermore, we formally prove the correctness and polynomial complexity of the adapted algorithm. The obtained results contribute to restoring the polynomial-time resolution of the Flood-It Problem on co-comparability graphs and reinforce the importance of structural analysis in dynamic programming-based algorithms.