Induced subgraphs of bounded treewidth and the container method

W pracy pokazujemy, że wiele naturalnych problemów, w tym problem największego zbioru niezależnego czy problem najmniejszego zbioru przecinającego wszystkie cykle, można rozwiązać w czasie wielomianowym w grafach, które nie zawierają indukowanej ścieżki o 5 wierzchołkach oraz w grafach, które nie zawierają indukowanego cyklu o co najmniej 5 wierzchołkach.

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By Pt we denote a path on t vertices. In this paper we give polynomial-time algorithms for the following problems: • the Maximum Weight Independent Set problem in long-hole-free graphs, and • the Feedback Vertex Set problem in P5-free graphs