Winning Cores in Parity Games

Steen Vester

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


We introduce the novel notion of winning cores in parity games and develop a deterministic polynomial-time under-approximation algorithm for solving parity games based on winning core approximation. Underlying this algorithm are a number properties about winning cores which are interesting in their own right. In particular, we show that the winning core and the winning region for a player in a parity game are equivalently empty. Moreover, the winning core contains all fatal attractors but is not necessarily a dominion itself. Experimental results are very positive both with respect to quality of approximation and running time. It outperforms existing state-of-the-art algorithms significantly on most benchmarks.
Original languageEnglish
Title of host publicationProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS '16)
PublisherAssociation for Computing Machinery
Publication date2016
ISBN (Print)978-1-4503-4391-6
Publication statusPublished - 2016
Event31st Annual ACM/IEEE Symposium on Logic in Computer Science - New York, United States
Duration: 5 Jul 20168 Jul 2016
Conference number: 31


Conference31st Annual ACM/IEEE Symposium on Logic in Computer Science
Country/TerritoryUnited States
CityNew York
SponsorAssociation for Computing Machinery, European Association for Computer Science Logic, IEEE
Internet address


  • Parity Games
  • Winning Cores
  • Algorithms
  • Computational Complexity


Dive into the research topics of 'Winning Cores in Parity Games'. Together they form a unique fingerprint.

Cite this