2026-07-22T05:41:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19714 2024-03-11T06:37:03Z ddc:004 open_access

Max Weight Independent Set in Sparse Graphs with No Long Claws Abrishami, Tara Chudnovsky, Maria Pilipczuk, Marcin Rzążewski, Paweł Max Weight Independent Set subdivided claw hereditary classes We revisit the recent polynomial-time algorithm for the Max Weight Independent Set (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Chudnovsky, Dibek, Rzążewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^{𝒪(Δ²)}, where n is the number of vertices of the instance and Δ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tara Abrishami and Maria Chudnovsky and Marcin Pilipczuk and Paweł Rzążewski 2024 Is Part Of LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2024.4 urn:nbn:de:0030-drops-197148 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.4 eng https://creativecommons.org/licenses/by/4.0/legalcode