Parity games on undirected graphs

We examine the complexity of solving parity games in the special case when the underlying game graph is undirected. For strictly alternating games, that is, when the game graph is bipartite between the players, we observe that the solution can be computed in linear time. In contrast, when the assumption of strict alternation is dropped, we show that the problem is as hard in the undirected case as it is in the general, directed, case.

► We examine the complexity of parity games when the game graph is undirected. ► For strictly alternating games, the solution can be computed in linear time. ► In the general case the problem is as hard as in the directed, case.