Constant Approximating k-Clique is W[1]-hard

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 $\ne$ 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)\operatorname{poly}(n)$ for some computable
function $f$. Unfortunately, assuming W[1] $\ne$ 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.

Speaker Bio

Bingkai Lin is a professor in the Theory Group in the Department of Computer Science and Technology at Nanjing University. Prior to joining Nanjing University, he was a researcher at National Institute of Informatics. He obtained his PhD degree at the University of Tokyo in 2016. He received his Master and Bachelor’s degree at Shanghai Jiao Tong University in 2013 and 2010 respectively. His primary research interests are parameterized complexity and algorithms.

Online Meeting

ZOOM ID: 467 156 1455

Password: 图灵机被提出的年份（4位）

Livestream

http://live.bilibili.com/22528138