Constant Approximating k-Clique is W[1]-hard (Bingkai Lin)


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.


2021-06-18  11:00-11:30    


Bingkai Lin, Nanjing University


Guangdong Hotel Shanghai