Reduction from Triangle Detection to Disjunctive coBüchi Objectives
Jump to navigation
Jump to search
FROM: Triangle Detection TO: Disjunctive coBüchi Objectives
Description
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.