Augmenting approach for some Maximum Set problems

The method of augmenting graphs is a general approach to solve the Maximum Independent Set problem. Our objective is to employ this approach to develop polynomial-time algorithms for some so-called Maximum Set problems, i.e. problems which can be stated as follows. Given a (simple) graph GG, find a maximum vertex subset SS of GG such that the subgraph induced by SS satisfies a given property ΠΠ. Such problems were shown to be NP-hard in general if the properties considered are non-trivial and hereditary Lewis and Yannakakis (1980) and Yannakakis (1978). In this paper, using the augmenting graph technique, we describe a graph class, in which some problems can be solved in polynomial time. We also prove the NP-hardness of some Maximum Set problems where the considered properties are not hereditary.