Max Weight Independent Set in sparse graphs with no long claws

Abstract

For graphs \(G\) and \(H\) , we say that \(G\) is \(H\) -free if it does not contain \(H\) as an induced subgraph. Already in the early 1980s Alekseev observed that the Max Weight Independent Set problem ( MWIS ) remains NP -hard in \(H\) -free graphs, unless every component of \(H\) is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then, determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. In this paper we make an important step towards solving the problem by providing a polynomial-time algorithm for MWIS in graphs excluding a fixed graph forest of paths and subdivided claws as an induced subgraph, and a fixed biclique as a subgraph.