Attractors Is All You Need: Parity Games In Polynomial Time

2025/11/04 by van der Heijden, Rick
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2511.03752

Abstract

This paper provides a polynomial-time algorithm for solving parity games that runs in O(n²⋅(n + m)) time-ending a search that has taken decades. Unlike previous attractor-based algorithms, the presented algorithm only removes regions with a determined winner. The paper introduces a new type of attractor that can guarantee finding the minimal dominion of a parity game. The attractor runs in polynomial time and can peel the graph empty.

Citations

• Improved Complexity Analysis of Quasi-Polynomial Algorithms Solving Parity Games
• Parity Games: Another View on Lehtinen's Algorithm
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space
• Exponential Lower Bounds For Policy Iteration

Related

• Fatal Attractors in Parity Games: Building Blocks for Partial Solvers
• Reachability Games and Parity Games
• Universal Algorithms for Parity Games and Nested Fixpoints
• A symmetric attractor-decomposition lifting algorithm for parity games
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time