Maximum weight independent sets in hole- and dart-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. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n3) O ( n 3 ) -time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n4) O ( n 4 ) -time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs.
hole-free graphs graph algorithms maximum weight independent set problem clique separators