[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium May 2 - back in attendance.

["I.Brunke" <i.brunke@fu-berlin.de>]

Dear all,

next Monday's Lecture and Colloquium will take place on May 2, back in attendance, at 14:15 h & 16:00 h at HU Berlin.

You all are cordially invited.

Location:

Humboldt-Kabinett - between House 3&4
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
Johann von Neumann-Haus - 1st Floor [British Reading]

Time: Monday, May 2 - 16:00 s.t.

Colloquium: Jana Novotna (University of Warsaw)

Title: Taming Creatures

Abstract:

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.

Virenfrei. www.avast.com