Parity Games with Partial Information Played on Graphs of Bounded Complexity

Speaker

Bernd Puchala, Mathematical Foundations of Computer Science

Title Parity Games with Partial Information Played on Graphs of Bounded Complexity
When 06.05.2010
Where Lecture Room Informatik 11
Abstract We address the strategy problem for parity games with partial information and observable colors, played on finite graphs of bounded graph complexity. We consider several measures for the complexity of graphs and we analyze in which cases, bounding the measure decreases the complexity of the strategy problem on the corresponding classes of graphs. We prove or disprove that the usual powerset construction which turns a game with partial information into a game with full information preserves boundedness of the graph complexity measure.

For the case where the partial information is unbounded we prove that the powerset construction does not preserve boundedness of any measure we consider. We also prove that the strategy problem is EXPTIME-hard on graphs with entanglement at most 2 and directed path-width at most 3 and that the problem is PSPACE-complete on acyclic graphs. For the case where the partial information is bounded we obtain that the powerset construction, while neither preserving boundedness of entanglement nor of (undirected) tree-width, does preserve boundedness of directed path-width. Therefore, parity games with bounded partial information, played on graphs with bounded directed path-width can be solved in polynomial time.

Slides download