Dear all, You all are cordially invited. Location: Johann von Neumann-Haus - 1st Floor [British Reading] Humboldt-Universität zu Berlin Rudower Chaussee 25 12489 Berlin Time: Monday, May 2 - 14:15 Lecture: Tomáš Masarik (Charles University Prague) Title: Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument Abstract:We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw St,t,t as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2O(n√logn) and a quasipolynomial-time approximation scheme with improved running time 2O(ε−1log5n). The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in Pt-free graphs, ensures that given an n-vertex Pt-free graph, in polynomial time we can find a set P of at most t−1 vertices, such that every connected component of G−N[P] has at most n/2 vertices. Our main technical contribution is an analog of this result for St,t,t-free graphs: given an n-vertex St,t,t-free graph, in polynomial time we can find a set P of O(tlogn) vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of G−N[P] such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most n/2 vertices. In the talk, we first show how Gyárfás' path argument works on Pt-free graphs. Then we will sketch-prove our main result with as few technical details as possible. Joint work with: Konrad Majewski, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski Coffee & Tea Break : outside Humboldt-Kabinett - between House 3&4 Time: Monday, May 2 - 16:00 s.t. Colloquium: Jana Novotna (University of Warsaw) Title: Taming Creatures A graph class is tame if it admits a polynomial bound on the number of minimal separators, and feral if it contains infinitely many graphs with exponential number of minimal separators. The former entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set, and many other problems, when restricted to an input graph from a tame class, by a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015]. In the talk, we show a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame and feral. To obtain the full dichotomy, we confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class C there exists a constant k such that no member of C contains a k-creature or a k-skinny-ladder as an induced minor, then there exists a polynomial p such that every graph G from C contains at most p(|V(G)|) minimal separators. Joint work with Jakub Gajarský, Lars Jafke, Paloma T. Lima, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza. |