Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/32196
Title: The Rabin Index of Parity Games: Its Complexity and Approximation
Authors: Huth, M.
Kuo, J. H-P.
Piterman, Nir
First Published: 25-Jun-2015
Publisher: Elsevier for Academic Press
Citation: Information and Computation Volume 245, December 2015, Pages 36–53
Abstract: 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 are identified 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 an EXPTIME 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 [17] on random and structured parity games and for the partial solver psolB [11] on random games.
DOI Link: 10.1016/j.ic.2015.06.005
ISSN: 0890-5401
Links: http://www.sciencedirect.com/science/article/pii/S0890540115000723
http://hdl.handle.net/2381/32196
Type: Journal Article
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
1-s2.0-S0890540115000723-main.pdfPublisher version609.19 kBAdobe PDFView/Open


Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.