2026-07-22T08:46:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16434 2024-03-06T10:57:28Z ddc:004 open_access

Max Weight Independent Set in Graphs with No Long Claws: An Analog of the Gyárfás' Path Argument Majewski, Konrad Masařík, Tomáš Novotná, Jana Okrasa, Karolina Pilipczuk, Marcin Rzążewski, Paweł Sokołowski, Marek Max Independent Set subdivided claw QPTAS subexponential-time algorithm We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw S_{t,t,t} as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomassé, SODA 2020] and provide a subexponential-time algorithm with improved running time 2^𝒪(√nlog n) and a quasipolynomial-time approximation scheme with improved running time 2^𝒪(ε^{-1} log⁵ n). The Gyárfás' path argument, a powerful tool that is the main building block for many algorithms in P_t-free graphs, ensures that given an n-vertex P_t-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 S_{t,t,t}-free graphs: given an n-vertex S_{t,t,t}-free graph, in polynomial time we can find a set P of 𝒪(t log n) 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Konrad Majewski and Tomáš Masařík and Jana Novotná and Karolina Okrasa and Marcin Pilipczuk and Paweł Rzążewski and Marek Sokołowski 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.93 urn:nbn:de:0030-drops-164343 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.93 eng https://creativecommons.org/licenses/by/4.0/legalcode