TY - GEN
T1 - Max Weight Independent Set in Sparse Graphs with No Long Claws
AU - Abrishami, Tara
AU - Chudnovsky, Maria
AU - Pilipczuk, Marcin
AU - Rzążewski, Paweł
N1 - Publisher Copyright:
© Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, and Paweł Rzążewski; licensed under Creative Commons License CC-BY 4.0.
PY - 2024/3
Y1 - 2024/3
N2 - 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 nO(∆2), 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.
AB - 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 nO(∆2), 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.
KW - Max Weight Independent Set
KW - hereditary classes
KW - subdivided claw
UR - http://www.scopus.com/inward/record.url?scp=85185507218&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85185507218&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.STACS.2024.4
DO - 10.4230/LIPIcs.STACS.2024.4
M3 - Conference contribution
AN - SCOPUS:85185507218
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024
A2 - Beyersdorff, Olaf
A2 - Kante, Mamadou Moustapha
A2 - Kupferman, Orna
A2 - Lokshtanov, Daniel
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024
Y2 - 12 March 2024 through 14 March 2024
ER -