Некоторые полные сложностные дихотомии для задачи о доминирующем множестве

Наследственный класс – множество обыкновенных графов, замкнутое относительно удаления вершин; каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданного размера, что каждая вершина вне подмножества имеет хотя бы одного соседа в данном подмножестве. Известна полная классификация алгоритмической сложности этой задачи для семейства наследственных классов, определяемых 5-вершинными минимальными порожденными запретами. В данной работе получены полные сложностные дихотомии для множеств запрещенных порожденных подграфов, каждый не более чем с 6 вершинами, содержащих путь на 5 вершинах или результат однократного подразбиения ребра звезды с 3 листьями.
Библиография: 17 названий.