(Almost) Settling the Complexity of Approximating Parameterized Dominating Set.

In this talk, we discuss the parameterized complexity of approximating the k-Dominating Set problem, where we are asked to decide whether an input graph G on n vertices has a dominating set of size F(k) * k in time T(k) * poly(n). In particular, we consider the question of whether there is an FPT-approximation algorithm for the k-Dominating Set problem. We show that, unless FPT=W[1], the k-Dominating Set problem admits no such FPT-approximation algorithm, for any non-decreasing functions F and T depending only on k (which can be tower functions). Furthermore, we show that, assuming ETH, the k-Dominating Set problem admits no (log n)^{1/k} approximation algorithm that runs in time n^{o(k)}. Our results are obtained from parameterized PCPs for k-Clique constructed by a simple coding technique. This is a joint work with Pasin Manurangsi (UC Berkeley) and Karthik CS (Weizmann Institute of Science), and it is a continuation of a talk from Parinya, which shows the same result under Gap-ETH.Non UBCUnreviewedAuthor affiliation: Simons Institute for the Theory of Computing & Shanghai University of Finance and EconomicsPostdoctora