The Constant Inapproximability of the Parameterized Dominating Set Problem
The Constant Inapproximability of the Parameterized Dominating Set Problem
复制标题
DOI：
10.1109/focs.2016.61
复制
发表时间：
2015-10
期刊：
影响因子：
--
通讯作者：
Yijia Chen;Bingkai Lin
中科院分区：
文献类型：
--
作者：
Yijia Chen;Bingkai Lin
我们证明了没有FPT-算法可以逼近具有任意常数比的控制集问题，除非FPT = W[1]。我们的硬度降低是建立在第二作者最近的W[1]-硬度证明的biclique问题[25]。除其他外，这产生了一个没有PCP机制的证明，即经典的支配集问题在指数时间假设下没有多项式时间常数近似。
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 [25]. 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.