From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More.
Parinya ChalermsookMarek CyganGuy KortsarzBundit LaekhanukitPasin ManurangsiDanupon NanongkaiLuca TrevisanPublished in: SIAM J. Comput. (2020)
Keyphrases
- dominating set
- fixed parameter tractable
- facility location problem
- approximation algorithms
- np hard
- parameterized complexity
- np complete
- connected dominating set
- computational problems
- special case
- exact algorithms
- global constraints
- bounded treewidth
- lower bound
- optimal solution
- abstract argumentation
- linear programming
- conjunctive queries
- integer programming
- facility location
- linear program
- worst case
- branch and bound algorithm
- data exchange
- computational complexity
- constraint satisfaction problems