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 NP-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). (C) 2011 Elsevier B.V. All rights reserved.
hole-free graphs modular decomposition graph algorithms maximum weight independent set problem graph decomposition clique separator decomposition perfect graphs