On the parameterized complexity of approximating dominating set

摘要: We study the parameterized complexity of approximating k-Dominating Set (domset) problem where an integer k and a graph G on n vertices are given as input, goal is to find dominating set size at most F(k) · whenever has k. When such algorithm runs in time T(k)poly(n) (i.e., FPT-time) for some computable function T, it said be F(k)-FPT-approximation k-domset. Whether exists listed seminal book Downey Fellows (2013) one ”most infamous” open problems Parameterized Complexity. This work gives almost complete answer this question by showing non-existence under W[1]≠FPT further providing tighter running lower bounds stronger hypotheses. Specifically, we prove following every functions F constant e > 0: (i) Assuming W[1]≠FPT, there no k-domset, (ii) Exponential Time Hypothesis (ETH), F(k)-approximation k-domset that T(k)no(k) time, (iii) Strong (SETH), ≥ 2, T(k)nk − (iv) k-sum Hypothesis, 3, T(k) n⌈ k/2 ⌉ time. Previously, only ratio FPT-approximation algorithms were ruled out (log1/4 ek)-FPT-approximation ETH [Chen Lin, FOCS 2016]. Recently, any was shown gapETH [Chalermsook et al., 2017]. Note that, best our knowledge, bound form nδ absolute δ 0 known before even factor inapproximation ratio. Our results obtained establishing connection between communication hardness approximation, generalizing ideas from recent breakthrough Abboud al. [FOCS show approximation certain variant label cover problem, suffices devise specific protocol depends which hypothesis rely on. Each these turns either well studied or one; allows us easily apply techniques solve them.