Abstract
Deciding whether a graph contains ak-Clique is a well-known NP-hard problem. One approach to dealing with NP-hard problemis approximation algorithm. However, assuming NP≠P, no polynomial timealgorithm can approximate k-Clique to any factor within n^{1-/epsilon}. Anotherapproach is FPT-algorithm, i.e. algorithm with running time upper bounded byf(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 anyFPT-algorithm that can approximate k-Clique to (1-/epsilon) We give a negativeanswer to this question under the assumption that k-Clique problem has noFPT-algorithm.
Time
2021-06-18 11:00-11:30Speaker
Bingkai Lin, Nanjing UniversityRoom
Guangdong Hotel Shanghai
