[latexpage]

If you’ve read the last posts in the series, you might remember that solving a parity games means to determine the partition into winning sets for both players and to provide witnessing winning strategies on the sets.

In our today’s post, we’ll have a look at a polytime-equivalent variation. Assume that we have an algorithm $A$ that takes a parity game $G$ and computes the partition into winning sets without providing any witnessing winning strategies, i.e.

\[

(W_0,W_1) = A(G)

\]

The question is, can we easily (in the sense that the blow-up is only polynomial-time) create an algorithm $A’$ based on $A$ s.t. $A’$ additionally computes witnessing winning strategies? The answer is yes and the iterative algorithm is fairly easy:

$A'(G)$: $(W_0,W_1) := A(G)$ $E' := \{(v,w) \in E \mid v \in (V_0 \cap W_0) \cup (V_1 \cap W_1)\}$ $F := E \setminus E'$ While there are two edges in $E'$ with the same source Do $(v,w) := $pick one of such edges in $E'$ $(W_0',W_1') := A(G|_{(E' \cup F) \setminus \{(v,w)\}})$ if $W_0 = W_0'$ $E' := E' \setminus \{(v,w)\}$ else $E' := E' \setminus \{(v,u) \in E' \mid u \not= w\}$ return the trivial strategies in $G|_{E' \cup F}$ on the winning sets

The basic idea is to reduce the number of strategies for both players on their winning sets until only one strategy remains for each player while maintaining the invariant that after removing strategies there will still be winning strategies left.

We reduce the number of strategies by removing edges from nodes with more than one outgoing edge. Note that we only remove player 0 edges from nodes of the player 0 winning set and player 1 edges from nodes of the player 1 winning set.

Let $e$ be such an edge. Remove it from the game and solve it again using algorithm $A$. If the algorithm returns the same winning sets, we know that there is a winning strategy left for the controller of $e$ that doesn’t require $e$, so we can safely remove it for good. If the winning sets change after removing $e$, we know that $e$ is essential for the winning strategy, so we can remove all other edges except for $e$ emanating from that node.

As we can only remove edges linearly often, the blow-up of $A$ is linear.

In the next post of the series, we will consider a related problem: given a pair of (total) strategies for both players that are guaranteed to be winning on the respective winning sets (without being given the winning sets), can we determine the winning sets easily?