Dziura w grafie to indukowany cykl o długości co najmniej 4. Dziura jest długa, jeśli jej długość wynosi co najmniej 5. Przez P_n​ oznaczamy ścieżkę o n wierzchołkach. W niniejszej pracy przedstawiamy algorytmy wielomianowe dla następujących problemów: problemu największego zbioru niezależnego w grafach bez długich dziur oraz problemu najmniejszego zbioru wierzchołków przecinającego wszystkie cykle (feedback vertex set) w grafach bez ścieżek P_5. Każdy z powyższych wyników rozwiązuje odpowiadający mu długoletni otwarty problem.

Rozszerzona dziura to dziura na pięciu wierzchołkach z dodatkowym wierzchołkiem sąsiadującym z jednym lub dwoma kolejnymi wierzchołkami tej dziury. Niech G oznacza klasę grafów, które nie zawierają rozszerzonej dziury ani dziur o długości co najmniej 6 jako indukowanych podgrafów; klasa ta zawiera zarówno wszystkie grafy bez długich dziur, jak i wszystkie grafy bez indukowanej ścieżki P_5​. Pokazujemy, że dla danego grafu o n wierzchołkach (z wagami na wierzchołkach) oraz danej liczby całkowitej k, można w czasie wielomianowym znaleźć największy w sensie sumy wag indukowany podgraf o szerokości drzewiastej mniejszej niż k. Wynik ten implikuje oba wspomniane wcześniej rezultaty.

Aby osiągnąć ten cel, rozszerzamy metodę potencjalnych maksymalnych klik (PMCs) do kontenerów. Zostały one opracowane przez Bouchitté i Todincę [SIAM J. Comput., 31 (2001), s. 212–232] oraz rozszerzone przez Fomina, Todincę i Villangera [SIAM J. Comput., 44 (2015), s. 54–87]. Metoda ta pozwala rozwiązywać szeroki wachlarz problemów, w tym znajdowanie najcięższego indukowanego podgrafu o szerokości drzewiastej mniejszej niż k (dla ustalonego k), w czasie wielomianowym względem rozmiaru grafu i liczby potencjalnych maksymalnych klik.

Dalsze rozwinięcia metody, dostosowane do rozwiązania problemu największego zbioru niezależnego (np. dla grafów bez indukowanej ścieżki P_5​ [Lokshtanov, Vatshelle i Villanger, SODA 2014, s. 570–581] lub grafów bez indukowanej ścieżki P_6​ [Grzesik, Klimošová, Pilipczuk i Pilipczuk, ACM Trans. Algorithms, 18 (2022), s. 4:1–4:57]), polegają na ograniczeniu się do generowania jedynie specjalnie wybranego podzbioru wszystkich potencjalnych maksymalnych klik w grafie.

We wszystkich wspomnianych pracach ostatnim krokiem jest złożony algorytm programowania dynamicznego, którego przestrzeń stanów jest oparta na rozważanej liście potencjalnych maksymalnych klik. W niniejszej pracy modyfikujemy ten algorytm i pokazujemy, że wystarczy rozważyć jedynie kontener dla każdej potencjalnej maksymalnej kliki: nadzbiór, który nie zawiera żadnych dodatkowych wierzchołków z poszukiwanego rozwiązania. To wzmocnienie metody nie tylko pozwala uzyskać nasz główny wynik, ale również prowadzi do znaczących uproszczeń w rozumowaniu stosowanym w poprzednich pracach.