## Quasipolynomial upper and lower bounds for parity games

### Main objective

#### Give a unified and simple presentation the three quasipolynomial time algorithms

• The key combinatorial notions are universal graphs, universal trees and separating automata
• They are equivalent and of quasipolynomial size (upper and lower bounds)
Reports on

## Parity games Parity: the maximal priority appearing infinitely often is even

### Solving parity games

INPUT: A parity game and initial vertex $v_0$
QUESTION: Does Eve have a winning strategy from $v_0$?

Parameters: $n$ (number of vertices) and $d$ (number of priorities)

Best algorithms (Calude, Jain, Khoussainov, Li, and Stephan, then Jurdziński and Lazić, then Lehtinen) $$O(n^{\log(d)}) = O(d^{\log(n)})$$

### Positionality

Positional strategy $$\sigma : V \to E$$
Theorem: If Eve has a winning strategy in a parity game, she also has a positional winning strategy. The same holds for Adam.

## Universal graphs

Definition: A graph satisfies parity if all paths in the graph satisfy parity
Definition: A (graph) homomorphism is $\phi : V \to V'$ st $$(v,i,v') \in E \Longrightarrow (\phi(v),i,\phi(v')) \in E$$
Definition: A graph $U$ is $(n,d)$-universal if
• it satisfies parity
• all graphs of size $n$ with $d$ priorities satisfying parity can be homomorphically mapped into $U$

## Reduction to safety games

Let $G$ parity game, $U$ universal graph. Construct safety game $G \times U$: Eve chooses the evolution in $U$

Lemma: Eve has a winning strategy in $G$ if and only if she has a strategy to play forever in $G \times U$

Algorithm: Solve the safety game $G \times U$, complexity $n \cdot |U|$
Lemma: Eve has a winning strategy in $G$ if and only if she has a strategy to play forever in $G \times U$

Proof:
If Eve wins in $G$ she has a positional strategy. Then $G_{\sigma}$ embeds into $U$, induces a winning strategy in $G \times U$
If Eve wins in $G \times U$ then this strategy is winning in $G$ because $U$ satisfies parity

## Main results

Theorem:
• There exists a quasipolynomial universal graph (three constructions, one for each quasipolynomial time algorithm)
• All universal graphs have at least quasipolynomial size

Theorem: the following quantities are equal
• The smallest universal graph
• The smallest universal tree
• The smallest separating automaton

## Universal trees

Definition: A tree is $(n,h)$-universal if it embeds all trees of height $h$ with $n$ leaves $\qquad$ Fact: Universal trees are exactly saturated universal graphs!

## Upper bounds

We construct a $(n,h)$-universal tree. Inductively
• $T_\text{middle}$ a $(n,h-1)$-universal tree
• $T_\text{left}$ a $(\lfloor n/2 \rfloor,h)$-universal tree
• $T_\text{right}$ a $(n - 1 - \lfloor n/2 \rfloor,h)$-universal tree Fact: there exists a balanced node

## Lower bounds

$$g(n,h) = \sum_{d = 1}^n g(\lfloor n / d \rfloor,h-1)$$ Let $T$ a $(n,h)$-universal tree and $\delta \in [1,n]$.
Claim: the number of nodes at depth $h-1$ of degree $\ge \delta$ is at least $g(\lfloor n / \delta \rfloor,h-1)$. Claim: $T_\delta$ is $(\lfloor n / \delta \rfloor,h-1)$-universal