Reduction from OV to Generalized Büchi Games

FROM: OV TO: Generalized Büchi Games

Implications

assume: OVH
then: there is no $O(m^{2-\epsilon})$ or $O(\min_{1 \leq i \leq k} b_i \cdot (k \cdot m)^{1-\epsilon})$-time algorithm (for any $\epsilon > {0}$ for generalized Büchi games. In particular there is no such algorithm for deciding whether the winning set is non-empty or deciding whether a specifc vertex is in the winning set.

Year

2016

Reference

Chatterjee, K., Dvořák, W., Henzinger, M., & Loitzenbauer, V. (2016). Conditionally Optimal Algorithms for Generalized B\" uchi Games. arXiv preprint arXiv:1607.05850.

https://arxiv.org/pdf/1607.05850.pdf