Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:On the Parameterized Complexity of Approximating Dominating Set
Speaker:Bundit Laekhanukit
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Talk
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:MPI Audience
Language:English
Date, Time and Location
Date:Tuesday, 20 February 2018
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Bundit Laekhanukit
EMail:blaekhan@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Keywords:Hardness of Approximation, Parameterized Complexity, Dominating Set
Note:
Attachments, File(s):

Created:
Bundit Laekhanukit, 02/06/2018 02:10 PM
Last modified:
halma/MPII/DE, 01/31/2019 12:00 AM
  • Bundit Laekhanukit, 02/06/2018 02:10 PM -- Created document.