MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

On the Parameterized Complexity of Approximating Dominating Set

Bundit Laekhanukit
Max-Planck-Institut für Informatik - D1
Talk
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
MPI Audience
English

Date, Time and Location

Tuesday, 20 February 2018
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

This talk concerns the parameterized complexity of approximating the k-Dominating Set problem:


Given a graph G on n vertices with a promise that G has a dominating set of size k, is there a t(k) * poly(n) time algorithm that outputs a dominating set of size f(k) * k?

We will give a negative answer to this question by showing that unless FPT=W[1] such algorithm does not exist. We further rule out n^{o(k)}-time and n^{k-c}-time (log n)^{1/poly(k)}-approximation algorithms for k-Dominating Set for any c>0 under ETH and SETH, respectively.

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].

Contact

Bundit Laekhanukit
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Hardness of Approximation, Parameterized Complexity, Dominating Set

Bundit Laekhanukit, 02/06/2018 14:10 -- Created document.