O jogo da coloração gulosa: explorando a pspace-completude com 3 cores

Abstract

In the field of Computer Science, there are mathematical games and puzzles of great interest to be analyzed. As an example, we have Graph Coloring Games, where some of these games involve coloring the vertices of a graph following predefined rules. These games raise questions that can be explored regarding their computational complexity. In this work, we focus on the Greedy Coloring Game, a turn-based game where two players, Alice and Bob, take turns coloring the vertices of a graph such that adjacent vertices have distinct colors. The colors are non-negative integers, and when a player chooses a vertex to color, the smallest available color must be used. The set of colors Cr is finite, and Alice wins if all vertices are colored using only the colors in Cr. Bob wins if he forces the use of more colors than those available in Cr. The Greedy Coloring Game was introduced in 2013 by Havet and Zhu, who presented results on game-related parameters. In 2020, Costa et al. proved the PSPACE-completeness of the game in the version where Alice starts, but with a large number of colors in Cr, even for small problem instances. In this work, we explore polynomial reductions of known problems (POS-CNF and POS-CNF-6) to graphs, seeking strategies to prove the complexity of the 3-color version where Bob initiates the Greedy Coloring Game. Through Lemma 5.4.1, which proves that cycles of size n ≥ 5 require 3 colors in the greedy game, we identified a challenge in the POS-CNF reduction: for long clauses, Bob can always win by following a specific strategy. For the POS-CNF-6 reduction and água-viva graphs (graphs containing an induced C6 and P3 subgraphs attached to the C6), we identified problematic game configurations when Alice assigns values to adjacent literals in a clause. We implemented a playable version of the Greedy Coloring Game (player vs Artificial Intelligence) using the MiniMax algorithm, which simulates all possible moves and aids in studying complex configurations. We conclude that the PSPACE-completeness with 3 colors remains open. However, our work advances the field by identifying critical configurations in polynomial reductions (long clauses, adjacent literals), establishing theoretical bounds with Lemma 5.4.1, and providing practical tools (MiniMax implementation and interactive game) for future testing.