BEGIN:VCALENDAR
CALSCALE:GREGORIAN
PRODID:iCalendar-Ruby
VERSION:2.0
BEGIN:VEVENT
DESCRIPTION: We revisit recent developments for the Maximum Weight Indepen
dent Set problem in graphs excluding a subdivided claw St\,t\,t as an indu
ced subgraph [Chudnovsky\, Pilipczuk\, Pilipczuk\, Thomassé\, SODA 2020] a
nd provide a subexponential-time algorithm with improved running time 2O(n
√logn) and a quasipolynomial-time approximation scheme with improved runni
ng 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 s
et 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 appropri
ate analog of a connected component to recurse on) of the said extended st
rip 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-pr
ove our main result with as few technical details as possible. Joint wo
rk with: Konrad Majewski\, Jana Novotná\, Karolina Okrasa\, Marcin Pilipcz
uk\, Paweł Rzążewski\, Marek Sokołowski
DTSTAMP:20220427T002900
DTSTART:20220502T141500
CLASS:PUBLIC
LOCATION:Humboldt-Universität zu Berlin\n Institut für Informatik\n Humbold
t-Kabinett (between House 3&4 / 1st Floor [British Reading])\n Johann von N
eumann-Haus\n Rudower Chaussee 25\n 12489 Berlin
SEQUENCE:0
SUMMARY:Tomáš Masarik (Charles University Prague): Max Weight Independent S
et in graphs with no long claws: An analog of the Gyárfás'\; path argum
ent
UID:107920262@www.facetsofcomplexity.de
URL:http://www.facetsofcomplexity.de/monday/20220502-L-Masarik.html
END:VEVENT
END:VCALENDAR