Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Friday, November 14, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G11

Speaker: Matthias Mnich (Universität Bonn)

A faster algorithm for parity games

Solving parity games is an important algorithmic task to problems in automated verification and controller synthesis. The model-checking problem for the modal $\mu$-calculus is known to be equivalent to parity game solving, and problems like validity or satisfiability for modal logics can be reduced to parity game solving. It is a major open problem whether a polynomial-time algorithm for solving parity games exists. To date, the fastest known algorithm runs in time $(n+m)^{O(\sqrt{n + m})}$, where $n$ denotes the number of nodes in the parity game controlled by the even player and $m$ denotes the number of nodes controlled by the odd player. This algorithm is due to Jurdziński, Paterson and Zwick (SODA 2006, SICOMP 2008). We give a faster algorithm for solving parity games, in time $(n+m)^{O(\sqrt{\min(m,n)})}$.

Joint work with H. Röglin and C. Rösner.

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login