direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Independent Set in P_t-free graphs

Tomohiro Koana (TU Berlin)


The independent set problem is known to be NP-hard in general. There has been an enormous interest in the problem restricted to Pt-free graphs, where Pt is an induced path of order t. It has long been known that the problem can be solved in polynomial time for P4-free graphs. Recently, there was a breakthrough by Lokshtanov et al. (SODA 2014), who showed that  the problem can be solved in polynomial time on P5-free graphs as well. Followed by this positive result, Grzesik et al. (arXiv 2017) extended the result to P6-free graphs. In this talk, two subexponential time algorithms for the independent set problem in Pt-free (for any fixed t) graphs are going to be presented.


Tomohiro Koana
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras