Almost polynomial factor inapproximability for parameterized k-clique
Almost polynomial factor inapproximability for parameterized k-clique
复制标题
DOI：
10.4230/lipics.ccc.2022.6
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
C. Karthik;Subhash Khot
中科院分区：
文献类型：
--
作者：
C. Karthik;Subhash Khot
k-Clique问题是一个参数化复杂性的典型困难问题。本文研究了k-团问题的参数化复杂性，其中给定一个整数k和一个n阶图G作为输入，目标是当图G有一个团的大小为k时，找到一个团的大小至少为k/F（k）.当这样的算法在时间T（k）· poly（n）中运行时（即，FPT-时间），它被称为是一个F（k）-FPT-近似算法的k-团问题。尽管在gap-ETH下已知不存在用于任何可计算次线性函数F的F（k）-FPT近似算法[Chalermsook等人，FOCS 2017]，在更标准和更弱的假设W[1] FPT下证明相同的不可逼近性结果仍然是一个长期存在的开放问题。在最近的一项突破中，Lin [STOC 2021]排除了常数因子（即，F（k）= O（1））在W[1]≠FPT下的FPT-逼近算法。在本文中，我们改进了这个不可逼近性结果（在同样的假设下），从而排除了对任何递增可计算函数H（例如H（k）= log* k）的每一个F（k）= k1/H（k）因子FPT-逼近算法.我们的主要技术贡献是将大素域上Hadamard码的列表译码引入到Lin的证明框架中。
The k-Clique problem is a canonical hard problem in parameterized complexity. In this paper, we study the parameterized complexity of approximating the k-Clique problem where an integer k and a graph G on n vertices are given as input, and the goal is to find a clique of size at least k/F(k) whenever the graph G has a clique of size k. When such an algorithm runs in time T(k) · poly(n) (i.e., FPT-time) for some computable function T, it is said to be an F(k)-FPT-approximation algorithm for the k-Clique problem. Although, the non-existence of an F(k)-FPT-approximation algorithm for any computable sublinear function F is known under gap-ETH [Chalermsook et al., FOCS 2017], it has remained a long standing open problem to prove the same inapproximability result under the more standard and weaker assumption, W[1]≠FPT. In a recent breakthrough, Lin [STOC 2021] ruled out constant factor (i.e., F(k) = O(1)) FPT-approximation algorithms under W[1]≠FPT. In this paper, we improve this inapproximability result (under the same assumption) to rule out every F(k) = k1/H(k) factor FPT-approximation algorithm for any increasing computable function H (for example H(k) = log* k). Our main technical contribution is introducing list decoding of Hadamard codes over large prime fields into the proof framework of Lin.