The Constant Inapproximability of the Parameterized Dominating Set Problem (Bingkai Lin)


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.


2016-07-01  14:00 ~ 15:00   


Bingkai Lin,Postdoctoral Researcher at the National Institute of Informatics


Room 102,School of Information Management & Engineering, Shanghai University of Finance & Economics