Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями

Задача о независимом множестве разрешима за полиномиальное время для графов, не содержащих пути $P_k$ при любом фиксированном $k$. Если же запрещается порождённый путь $P_k$, то при $k>6$ сложностной статус этой задачи неизвестен. Рассматриваются промежуточные случаи, когда запрещён порождённый путь $P_k$ и некоторые его остовные надграфы. Доказывается полиномиальная разрешимость задачи о независимом множестве в следующих случаях: 1) запрещаются надграфы, у которых минимальная степень вершины меньше $k/2$; 2) запрещаются надграфы, у которых дополнительный граф имеет более $k/2$ рёбер; 3) запрещаются надграфы, из которых с помощью операции пересечения графов можно получить $P_k$. Библиогр. 12.