2015/10/31 by Yijia Chen, Chen, Yijia, Bingkai Lin +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC
paper · pdf · doi:10.48550/arxiv.1511.00075
openalex publication_date 2015/10/31 · arxiv created 2015/11/15 · arxiv updated 2015/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT= W[1]. Our hardness reduction is built on the second author's recent W[1]-hardness proof of the biclique problem. This yields, among other things, a proof without the PCP machinery that the classical dominating set problem has no polynomial time constant approximation under the exponential time hypothesis.