On the Parameterized Complexity of Approximating Dominating Set

We study the parameterized complexity of approximating the k -Dominating 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 W1 ≠ 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: • Assuming W1 ≠ FPT, there is no F ( k )- FPT-approximation algorithm for k -DomSet. • Assuming the Exponential Time Hypothesis (ETH), there is no F ( k )-approximation algorithm for k -DomSet that runs in T ( k ) ⋅ n o ( k ) time. • 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. • 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 sf W1 ≠ FPT and (log 1/4 this allows us to easily apply known techniques to solve them.