Attractors Is All You Need: Parity Games In Polynomial Time

This paper provides a polynomial-time algorithm for solving parity games that runs in $\mathcal{O}(n^2\cdot (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.