MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Independent Set on H-free Graphs

Erik Jan van Leeuwen
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 1 December 2015
13:00
30 Minutes
E1 4
024
Saarbrücken

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

Erik Jan van Leeuwen
--email hidden
passcode not visible
logged in users only

Erik Jan van Leeuwen, 11/18/2015 13:45 -- Created document.