## Abstract

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

Original language | English (US) |
---|---|

Title of host publication | STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing |

Editors | Monika Henzinger, David Kempe, Ilias Diakonikolas |

Publisher | Association for Computing Machinery |

Pages | 815-826 |

Number of pages | 12 |

ISBN (Electronic) | 9781450355599 |

DOIs | |

State | Published - Jun 20 2018 |

Externally published | Yes |

Event | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: Jun 25 2018 → Jun 29 2018 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 50th Annual ACM Symposium on Theory of Computing, STOC 2018 |
---|---|

Country/Territory | United States |

City | Los Angeles |

Period | 6/25/18 → 6/29/18 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

- Dominating set
- Parameterized inapproximability
- Set cover