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