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 条
[41]   An efficient matheuristic for the minimum-weight dominating set problem [J].
Albuquerque, Mayra ;
Vidal, Thibaut .
APPLIED SOFT COMPUTING, 2018, 72 :527-538
[42]   Liar's dominating set problem on unit disk graphs [J].
Jallu, Ramesh K. ;
Das, Gautam K. .
DISCRETE APPLIED MATHEMATICS, 2020, 286 :91-99
[43]   Optimal Metric Search Is Equivalent to the Minimum Dominating Set Problem [J].
Hetland, Magnus Lie .
SIMILARITY SEARCH AND APPLICATIONS, SISAP 2020, 2020, 12440 :111-125
[44]   DNA computing for a dominating set problem based on sticker models [J].
Yin, Zhixiang ;
Cui, Jianzhong ;
Yang, Yan ;
Ma, Yin ;
Wang, Wei ;
Yang, Jin ;
Sun, Xia .
KYBERNETES, 2012, 41 (09) :1343-1350
[45]   A complexity dichotomy and a new boundary class for the dominating set problem [J].
Malyshev, D. S. .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 32 (01) :226-243
[46]   On a Countable Family of Boundary Graph Classes for the Dominating Set Problem [J].
Dakhno G.S. ;
Malyshev D.S. .
Journal of Applied and Industrial Mathematics, 2023, 17 (01) :25-31
[47]   TREE-SEARCH ALGORITHMS FOR THE DOMINATING VERTEX SET PROBLEM [J].
TSOUROS, C ;
SATRATZEMI, M .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1993, 47 (3-4) :127-133
[48]   A complexity dichotomy and a new boundary class for the dominating set problem [J].
D. S. Malyshev .
Journal of Combinatorial Optimization, 2016, 32 :226-243
[49]   Towards efficient local search for the minimum total dominating set problem [J].
Hu, Shuli ;
Liu, Huan ;
Wang, Yupan ;
Li, Ruizhi ;
Yin, Minghao ;
Yang, Nan .
APPLIED INTELLIGENCE, 2021, 51 (12) :8753-8767
[50]   The dominating set problem is fixed parameter tractable for graphs of bounded genus [J].
Ellis, J ;
Fan, H ;
Fellows, M .
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2004, 52 (02) :152-168
12345