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

Математические заметки. 2025. Т. 117. № 1. С. 62–78.

Дахно Г. С., Малышев Д. С.

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

Ключевые слова: наследственный класс, вычислительная сложность, доминирующее множество

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Cетевые модели, оптимизация и вычислительная сложность (2024)