1
$\begingroup$

Parity games are simple games played on a graph: https://en.m.wikipedia.org/wiki/Parity_game

Let $A$ be an algorithm that solves the following problem in polynomial time.

Given: A graph $G=(V,E)$ with $V=V_0\cup V_1$ and a coloring of the vertices according to the priorities.

Question: Does $G$ have a winning region for the player Even?

In other words, is there a vertex such that player Even has a winning strategy from this vertex or are all vertices winning positions for player Odd?

Can we use $A$ as a subroutine to solve general parity games in polynomial time?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes.

Here is how it works: If Player Odd always wins, we are done.

Otherwise, we remove one choice of Player Even at a time and ask if Player even still wins from somewhere. If the answer is ever "no", we fix that particular choice for Player Even. As parity games are positionally determined, Player Even only needs one choice per vertex.

This process leads, after no more rounds than there are edges, to a game where Player Even has a single remaining choice anywhere she plays, and where she wins somewhere. Single-player parity games are solvable in polynomial time, so we can find out where she wins. We remove the newly identified winning region for Player Even from the graph, and start over. This outer loop is repeated for at most the number of vertices, so its still polynomial time overall.

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.