On 28.03.2019 at 12:30 in S6, there is the following noon lecture:
Algorithms for graphs without linear forests
KAM, MFF, Charles University
Many graph problems that are NP-hard in general are solvable on polynomial time when we restrict ourselves to a class of H-free graphs, that is, graphs without an induced copy of a fixed graph H. In my talk I will focus on two such problems - Maximum Weight Independent Set and 3-Colouring. Both problems are known to be NP-hard even for graphs of large girth, thus, one can only hope to find a polynomial time algorithm for H-free graphs when H is a forest.
I will present a polynomial-time algorithm for Maximum Weight Independent Set problem on P6-free graphs, that is, graphs that has no path on 6 vertices as an induced subgraph and a polynomial-time algorithm for 3-Colouring for P2+P5-free graphs and for P3+P4-free graphs, where Pr+Ps is the disjoint union of paths on r and s vertices. The latter result together with previously known results yields complete complexity classification of 3-Colouring on H-free graphs for all graphs H on up to seven vertices.
The talk includes joint results with Andrzej Grzesik, Marcin Pilipczuk and Michał Pilipczuk and with Josef Malík, Tomáš Masařík, Jana Novotná, Daniël Paulusma and Veronika Slívová.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019