Maximum Weight Independent Sets in hole- and co-chair-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. Being one of the most investigated and most important problems on graphs, it is well known to be NPNP-complete and hard to approximate. The complexity of MWIS is open for hole-free graphs (i.e., graphs without induced subgraphs isomorphic to a chordless cycle of length at least five). By applying a combination of clique separator and modular decomposition, we obtain a polynomial time solution of MWIS for hole- and co-chair-free graphs (the co-chair consists of five vertices four of which form a clique minus one edge – a diamond – and the fifth has degree one and is adjacent to one of the degree two vertices of the diamond).

► The Maximum Weight Independent Set (MWIS) problem on graphs is a frequently studied problem.
► Clique separators and modular decomposition are powerful tools for solving this problem on various graph classes.
► We combine these tools for solving MWIS efficiently on hole- and co-chair-free graphs.
► In particular, we show that prime atoms of those graphs are nearly weakly chordal.