Max Weight Independent Set in sparse graphs with no long claws

2023/09/29 by Abrishami, Tara, Chudnovsky, Maria, Dibek, Cemil +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2309.16995

Abstract

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, Dibek, Chudnovsky, Rzążewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time n^O(Δ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.

Cited by

• Graph Classes Closed under Self-intersection

Related

• Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws
• Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time
• Maximum Weight Independent Set in lClaw-Free Graphs in Polynomial Time
• Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs