In a finite undirected graph, an
apple consists of a chordless cycle of length at least 4, and an additional vertex which is not in the cycle and sees exactly one
of the cycle vertices. A graph is
apple-free if it contains no induced subgraph isomorphic to an apple. Apple-free graphs are a common generalization of chordal graphs,
claw-free graphs and cographs and occur in various papers. The Maximum Weight Independent Set (MWS) problem is efficiently
solvable on chordal graphs, on cographs as well as on claw-free graphs. In this paper, we obtain partial results on some subclasses
of apple-free graphs where our results show that the MWS problem is solvable in polynomial time. The main tool is a combination
of clique separators with modular decomposition.
Our algorithms are robust in the sense that there is no need to recognize whether the input graph is in the given graph class;
the algorithm either solves the MWS problem correctly or detects that the input graph is not in the given class.
Keywords Apple-free graphs - Clique separators - Nearly perfect graphs - Nearly chordal graphs - Efficient algorithms - Maximum Weight Independent Set problem