Imperial College London
Portrait Picture

ProfessorMichaelHuth

Faculty of Engineering, Department of Computing

Head of the Department of Computing
 
 
 
//

Contact

 

m.huth Website

 
 
//

Location

 

Huxley 566Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Huth:2015:10.1016/j.ic.2015.06.005,
author = {Huth, MRA and Piterman, N and Kuo, JH-P},
doi = {10.1016/j.ic.2015.06.005},
journal = {Information and Computation},
pages = {36--53},
title = {The Rabin Index of Parity Games: Its Complexity and Approximation},
url = {http://dx.doi.org/10.1016/j.ic.2015.06.005},
volume = {245},
year = {2015}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colorings of game graphs areidentified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in P for k=1$but NP-hard for all fixed k >= 2. We present anEXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output over-approximates the Rabin index in polynomial time. We evaluate this efficient algorithm as a preprocessor of solvers in detailed experiments: for Zielonka's solver on random and structured parity games and for partial solver psolB on random games.
AU  - Huth,MRA
AU  - Piterman,N
AU  - Kuo,JH-P
DO  - 10.1016/j.ic.2015.06.005
EP  - 53
PY  - 2015///
SN  - 1090-2651
SP  - 36
TI  - The Rabin Index of Parity Games: Its Complexity and Approximation
T2  - Information and Computation
UR  - http://dx.doi.org/10.1016/j.ic.2015.06.005
UR  - http://hdl.handle.net/10044/1/21559
VL  - 245
ER  -
Download