The recent publications in the field of computational complexity and game theory reveal a significant focus on the exploration of algorithmic challenges within various models of computation and game structures. A notable trend is the investigation into the computational hardness of problems, particularly those that are NP-hard or PSPACE-complete, across different contexts such as video games, temporal graphs, and vector addition systems with states (VASS). Researchers are pushing the boundaries of understanding by characterizing the tractability borders of these problems, especially when inputs are encoded in unary or binary, and by developing polynomial-time algorithms for specific instances. Additionally, there is a continued interest in solving games on temporal graphs and the parity index problem of tree automata, with advancements in simplifying proofs and extending game-based approaches to tackle these complex issues.

Noteworthy Papers

• Computational Complexity of Game Boy Games: Demonstrates the NP-hardness of generalized versions of popular Game Boy games through Karp reductions from classic NP-complete problems.
• Temporal Explorability Games: Reveals that the complexity of explorability games on temporal graphs aligns with generalized reachability, highlighting the impact of edge availability specification and adversary presence.
• The Tractability Border of Reachability in Simple Vector Addition Systems with States: Characterizes the NP-hardness of reachability in unary encoded 3-VASS and presents a polynomial-time algorithm for 2-SLPS with binary configurations.
• Mostowski Index via extended register games: Introduces parity transduction games to address the parity index problem of tree automata, offering a simplified proof based on Lehtinen's quasipolynomial algorithm for parity games.