Abstract
Deciding whether a graph contains a k-Clique is a well-known NP-hard problem. One approach to dealing with NP-hard problem is approximation algorithm. However, assuming NP≠P, no polynomial time algorithm can approximate k-Clique to any factor within n^{1-\epsilon}. Another approach is FPT-algorithm, i.e. algorithm with running time upper bounded by f(k)poly(n) for some computable function f. Unfortunately, assuming W[1]≠FPT, the k-Clique problem has no FPT-algorithm. A natural question is: Is there any FPT-algorithm that can approximate k-Clique to (1-\epsilon) We give a negative answer to this question under the assumption that k-Clique problem has no FPT-algorithm.
Time
2021-06-18 11:00-11:30Speaker
Bingkai Lin, Nanjing UniversityRoom
Guangdong Hotel Shanghai
