Reduction from Triangle Detection to Disjunctive coBüchi Objectives
Revision as of 12:19, 15 February 2023 by Admin (talk | contribs) (Created page with "FROM: Triangle Detection TO: Disjunctive coBüchi Objectives == Description == == Implications == assume: Strong Triangle<br/>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 == Refer...")
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.