{"ID":2846416,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.03752","arxiv_id":"2511.03752","title":"Attractors Is All You Need: Parity Games In Polynomial Time","abstract":"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.","short_abstract":"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 attrac...","url_abs":"https://arxiv.org/abs/2511.03752","url_pdf":"https://arxiv.org/pdf/2511.03752v1","authors":"[\"Rick van der Heijden\"]","published":"2025-11-04T21:54:11Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"cs.FL\",\"cs.GT\",\"cs.LO\"]","methods":"[]","has_code":false}