Title: Faster Algorithms for Mean-Payoff Parity Games,
Abstract: Graph games provide the foundation for modeling and synthesis of reactive
processes. Such games are played over graphs where the vertices are controlled
by two adversarial players. We consider graph games where the objective of the
first player is the conjunction of a qualitative objective (specified as a
parity condition) and a quantitative objective (specified as a mean-payoff
condition). There are two variants of the problem, namely, the threshold
problem where the quantitative goal is to ensure that the mean-payoff value is
above a threshold, and the value problem where the quantitative goal is to
ensure the optimal mean-payoff value; in both cases ensuring the qualitative
parity objective. The previous best-known algorithms for game graphs with $n$
vertices, $m$ edges, parity objectives with $d$ priorities, and maximal
absolute reward value $W$ for mean-payoff objectives, are as follows:
$O(n^{d+1} \cdot m \cdot W)$ for the threshold problem, and $O(n^{d+2} \cdot m
\cdot W)$ for the value problem. Our main contributions are faster algorithms,
and the running times of our algorithms are as follows: $O(n^{d-1} \cdot m
\cdot W)$ for the threshold problem, and $O(n^{d} \cdot m \cdot W \cdot \log
(n\cdot W))$ for the value problem. For mean-payoff parity objectives with two
priorities, our algorithms match the best-known bounds of the algorithms for
mean-payoff games (without conjunction with parity objectives). Our results are
relevant in synthesis of reactive systems with both functional requirement
(given as a qualitative objective) and performance requirement (given as a
quantitative objective).