# Lecture by Tomáš Masarik (Charles University Prague): Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument

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

### Time & Location

May 02, 2022 | 02:15 PM

Humboldt-Universität zu Berlin

Institut für Informatik

Humboldt-Kabinett (between House 3&4 / 1st Floor [British Reading])

Johann von Neumann-Haus

Rudower Chaussee 25

12489 Berlin