Parameterized Algorithms for Parity Games
Gajarsky, Jakub; Lampis, Michael; Makino, Kazuhisa; Mitsou, Valia; Ordyniak, Sebastian (2015), Parameterized Algorithms for Parity Games, in Italiano, Giuseppe F.; Pighizzini, Giovanni; Sannella, Donald T., Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, Springer : Berlin Heidelberg, p. 336-347. 10.1007/978-3-662-48054-0_28
TypeCommunication / Conférence
Conference title40th International Symposium, MFCS 2015
Book titleMathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II
Book authorItaliano, Giuseppe F.; Pighizzini, Giovanni; Sannella, Donald T.
Number of pages615
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Research Institute for Mathematical Sciences [RIMS]
Institute of Information Systems
Abstract (EN)Determining the winner of a Parity Game is a major problem in computational complexity with a number of applications in verification. In a parameterized complexity setting, the problem has often been considered with parameters such as (directed versions of) treewidth or clique-width, by applying dynamic programming techniques.In this paper we adopt a parameterized approach which is more inspired by well-known (non-parameterized) algorithms for this problem. We consider a number of natural parameterizations, such as by Directed Feedback Vertex Set, Distance to Tournament, and Modular Width. We show that, for these parameters, it is possible to obtain recursive parameterized algorithms which are simpler, faster and only require polynomial space. We complement these results with some algorithmic lower bounds which, among others, rule out a possible avenue for improving the best-known sub-exponential time algorithm for parity games.
Subjects / Keywordsparity games; parameterized complexity
Showing items related by title and author.