The Constant Inapproximability of the Parameterized Dominating Set Problem

被引：13
作者：
Chen, Yijia [1 ]
Lin, Bingkai [2 ]
机构：
[1] Fudan Univ, Sch Comp Sci, Shanghai, Peoples R China
[2] JST, ERATO, Kawarabayashi Large Graph Project NII, Chiyoda Ku, 2-1-2 Hitotsubashi, Tokyo 1018430, Japan
来源：
2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS) | 2016年
关键词：
fpt inapproximability; dominating set; W[1; ETH; APPROXIMATION;
D O I：
10.1109/FOCS.2016.61
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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.
引用
收藏
页码：505 / 514
页数：10
相关论文
共 50 条
[21]   Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs [J].
de Figueiredo, Celina M. H. ;
Lopes, Raul ;
de Melo, Alexsander A. ;
Silva, Ana .
NETWORKS, 2024, 84 (02) :132-147
[22]   The fixed set search applied to the power dominating set problem [J].
Jovanovic, Raka ;
Voss, Stefan .
EXPERT SYSTEMS, 2020, 37 (06)
[23]   Statistical Mechanics of the Minimum Dominating Set Problem [J].
Zhao, Jin-Hua ;
Habibulla, Yusupjan ;
Zhou, Hai-Jun .
JOURNAL OF STATISTICAL PHYSICS, 2015, 159 (05) :1154-1174
[24]   Complete Complexity Dichotomies for the Dominating Set Problem [J].
G. S. Dakhno ;
D. S. Malyshev .
Mathematical Notes, 2025, 117 (1) :62-74
[25]   Statistical Mechanics of the Minimum Dominating Set Problem [J].
Jin-Hua Zhao ;
Yusupjan Habibulla ;
Hai-Jun Zhou .
Journal of Statistical Physics, 2015, 159 :1154-1174
[26]   An Approximation Algorithm for a Variant of Dominating Set Problem [J].
Wang, Limin ;
Wang, Wenqi .
AXIOMS, 2023, 12 (06)
[27]   Boundary classes of graphs for the dominating set problem [J].
Alekseev, VE ;
Korobitsyn, DV ;
Lozin, VV .
DISCRETE MATHEMATICS, 2004, 285 (1-3) :1-6
[28]   On the advice complexity of the online dominating set problem [J].
Bockenhauer, Hans-Joachim ;
Hromkovicc, Juraj ;
Krug, Sacha ;
Unger, Walter .
THEORETICAL COMPUTER SCIENCE, 2021, 862 :81-96
[29]   On-line algorithms for the dominating set problem [J].
King, GH ;
Tzeng, WG .
INFORMATION PROCESSING LETTERS, 1997, 61 (01) :11-14
[30]   PARAMETERIZED INAPPROXIMABILITY OF THE MINIMUM DISTANCE PROBLEM OVER ALL FIELDS AND THE SHORTEST VECTOR PROBLEM IN ALL ℓ p NORMS [J].
Bennett, Huck ;
Cheraghchi, Mahdi ;
Guruswami, Venkatesan ;
Ribeiro, Joao .
SIAM Journal on Computing, 2024, 53 (05) :1439-1475
12345