Containers for the maximum weight independent set problem

Let C be a class of graphs. We say that C has a "polynomial separator property" if there there exists a constant d such that for every G in C, the number of minimal separators in G is at most |V(G)|^d. It is known that the maximum weight independent set problem can be solved in polynomial time if the input graph belongs to a class of graphs that has the polynomial separator property.

Recently we were able to extend this result to the case when instead of having polynomially many minimal separators, the input graph has the property that all "important" minimal separators are contained in one of polynomially many containers (subsets of the vertex set); we call this a "polynomial container property".

We then show that the class of graphs with no hole of length at least five has the polynomial container property, thus providing a polynomial time algorithm to solve the maximum weight independent set problem for this class of graphs.

This is joint work with Tara Abrishami and Marcin Pilipczuk.