Open Collections

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

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: Simons Institute for the Theory of Computing & Shanghai University of Finance and Economics

2018-05-13

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65831

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/