BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

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


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.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International