Abstract
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 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.Time
2016-07-01 14:00 ~ 15:00Speaker
Bingkai Lin,Postdoctoral Researcher at the National Institute of InformaticsRoom
Room 102,School of Information Management & Engineering, Shanghai University of Finance & Economics
