The Maximum Independent Set Problem in Subclasses of Si,j,k-Free Graphs

We consider the Maximum Independent Set (MIS) problem, which is known to be NP-hard in general, in subclasses of Si,j,k-free graphs, where Si,j,k is the graph consisting of three induced paths of lengths i,j,k with a common initial vertex. We revise the complexity of the problem. Then by two general approaches, augmenting graph and α-redundant vertex, some graph classes, for which we have polynomial solutions, are obtained.