On a Countable Family of Boundary Graph Classes for the Dominating Set Problem

Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций"). 2023. Vol. 17. No. 1. P. 25–31.

G. S. Dakhno, D. S. Malyshev

Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, а имеется ли в нем такое подмножество вершин заданной мощности, что каждая вершина вне подмножества имеет хотя бы одного соседа в подмножестве. Ранее для данной задачи было известно ровно 4 граничных класса (если P!=NP). В этой работе рассматривается некоторое счетное множество конкретных классов графов и доказывается, что каждый его элемент является граничным классом для задачи о доминирующем множестве (если P!= NP). В ней доказывается NP-полнота данной задачи для графов, не содержащих порожденного 6-пути и 4-клики, что означает, что множество известных граничных классов для задачи о доминирующем множестве не является полным (если P!= NP). 

Ключевые слова: вычислительная сложность, наследственный класс графов, Computational Complexity, доминирующее множество, hereditary graph class

ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА: Современные подходы к анализу сетевых структур (2022)