## Nathanaël Fijalkow

### CNRS, LaBRI, Bordeaux, and The Alan Turing Institute of data science, London

## 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**)

## 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