babylonpolice.com

We improve the complexity of solving parity games (with priorities in
vertices) for $d={\omega}(\log n)$ by a factor of ${\theta}(d^2)$: the best
complexity known to date was $O(mdn^{1.45+\log_2(d/\log_2(n))})$, while we
obtain $O(mn^{1.45+\log_2(d/\log_2(n))}/d)$, where $n$ is the number of
vertices, $m$ is the number of edges, and $d$ is the number of priorities.

We base our work on existing algorithms using universal trees, and we improve
their complexity. We present two independent improvements. First, an
improvement by a factor of ${\theta}(d)$ comes from a more careful analysis of
the width of universal trees. Second, we perform (or rather recall) a finer
analysis of requirements for a universal tree: while for solving games with
priorities on edges one needs an $n$-universal tree, in the case of games with
priorities in vertices it is enough to use an $n/2$-universal tree. This way,
we allow to solve games of size $2n$ in the time needed previously to solve
games of size $n$; such a change divides the quasi-polynomial complexity again
by a factor of ${\theta}(d)$.