Yijia Chen (Fudan)

Title: The Constant Inapproximability of the Parameterized
Dominating Set Problem

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 Lin's recent
W[1]-hardness proof of the biclique problem [Lin, 2015]. 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.

This is joint work with Bingkai Lin (Tokyo).