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:Independent Set on H-free Graphs
Speaker:Erik Jan van Leeuwen
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 1 December 2015
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
H-free graphs are graphs without a fixed graph H as an induced subgraph. It is known that Independent Set is NP-hard if H is *not* a path or a subdivision of K1,3. It is unknown whether Independent Set becomes NP-hard on H-free graphs if H is a (very long) path. However, we do know that the problem is polynomial-time solvable when H is a path on at most 5 vertices. In this talk, we show that Independent Set can be solved in quasipolynomial time if H is a path on 6 vertices.

This talk is based on joint work with Daniel Lokshtanov and Marcin Pilipczuk, and will appear in SODA 2016.

Contact
Name(s):Erik Jan van Leeuwen
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Erik Jan van Leeuwen, 11/18/2015 01:45 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Erik Jan van Leeuwen, 11/18/2015 01:45 PM -- Created document.