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 条

[1] THE CONSTANT INAPPROXIMABILITY OF THE PARAMETERIZED DOMINATING SET PROBLEM
Chen, Yijia
Lin, Bingkai
SIAM JOURNAL ON COMPUTING, 2019, 48 (02) : 513 - 533
[2] Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
Liu, Chunmei
Song, Yinglei
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2011, 22 (04) : 684 - 698
[3] Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
Chunmei Liu
Yinglei Song
Journal of Combinatorial Optimization, 2011, 22 : 684 - 698
[4] Inapproximability of dominating set on power law graphs
Gast, Mikael
Hauptmann, Mathias
Karpinski, Marek
THEORETICAL COMPUTER SCIENCE, 2015, 562 : 436 - 452
[5] Parameterized dominating set problem in chordal graphs: complexity and lower bound
Liu, Chunmei
Song, Yinglei
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2009, 18 (01) : 87 - 97
[6] Parameterized dominating set problem in chordal graphs: complexity and lower bound
Chunmei Liu
Yinglei Song
Journal of Combinatorial Optimization, 2009, 18 : 87 - 97
[7] On the Parameterized Complexity of Approximating Dominating Set
Karthik, C. S.
Laekhanukit, Bundit
Manurangsi, Pasin
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 1283 - 1296
[8] On the Parameterized Complexity of Approximating Dominating Set
Karthik, C. S.
Laekhanukit, Bundit
Manurangsi, Pasin
JOURNAL OF THE ACM, 2019, 66 (05)
[9] Parameterized Inapproximability of Independent Set in H-Free Graphs
Pavel Dvořák
Andreas Emil Feldmann
Ashutosh Rai
Paweł Rzążewski
Algorithmica, 2023, 85 : 902 - 928
[10] Parameterized Inapproximability of Independent Set in H-Free Graphs
Dvorak, Pavel
Feldmann, Andreas Emil
Rai, Ashutosh
Rzazewski, Pawel
ALGORITHMICA, 2023, 85 (04) : 902 - 928

← 1 2 3 4 5 →