Clique-Width and Parity Games

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

OBDRŽÁLEK Jan

Year of publication 2007
Type Article in Proceedings
Conference Computer Science Logic 2007, proceedings
MU Faculty or unit

Faculty of Informatics

Citation
Field Informatics
Keywords parity games; mu-calculus; clique-width
Description The question of the exact complexity of solving parity games is one of the major open problems in system verification, as it is equivalent to the problem of model-checking the modal $\mu$-calculus. The known upper bound is NP$\cap$co-NP, but no polynomial algorithm is known. It was shown that on tree-like graphs (of bounded tree-width and DAG-width) a polynomial-time algorithm does exist. Here we present a polynomial-time algorithm for parity games on graphs of bounded clique-width (class of graphs containing e.g. complete bipartite graphs and cliques), thus completing the picture. This also extends the tree-width result, as graphs of bounded tree-width are a subclass of graphs of bounded clique-width. The algorithm works in a different way to the tree-width case and relies heavily on an interesting structural property of parity games.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.