Reduction from Triangle Detection to Disjunctive coBüchi Objectives

FROM: Triangle Detection TO: Disjunctive coBüchi Objectives

Implications

assume: Strong Triangle
then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k\cdot n^{2})^{1-\epsilon})$-time algorithm for any $epsilon > {0}$ for generalized Büchi games. In particular, there is no such algorithm deciding whether the winning set is non-empty or deciding whether a specific 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