Том 30, номер 1, 2023 г., Стр. 28-39

УДК 519.17
Дахно Г. С., Малышев Д. С.
О счетном семействе граничных классов графов для задачи о доминирующем множестве

Аннотация:
Наследственный класс — это множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задаётся множеством своих минимальных запрещённых порождённых подграфов. Если это множество конечно, то класс называется конечно определённым. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определённых классов. Задача о доминирующем множестве для заданного графа состоит в том, чтобы определить, имеется ли в нём такое подмножество вершин заданной мощности, что каждая вершина вне подмножества имеет хотя бы одного соседа в подмножестве. Ранее для данной задачи было известно ровно 4 граничных класса (если $\mathbb {P} \ne \mathbb {NP}$). В этой работе рассматривается некоторое счётное множество конкретных классов графов и доказывается, что каждый его элемент является граничным классом для задачи о доминирующем множестве (если $\mathbb {P} \ne \mathbb {NP}$). Также доказывается $\mathbb {NP}$-полнота данной задачи для графов, не содержащих порождённого 6-пути и 4-клики. Это означает, что множество известных граничных классов для задачи о доминирующем множестве не полное (если $\mathbb {P} \ne \mathbb {NP}$).
Библиогр. 11.

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

DOI: 10.33048/daio.2023.30.742

Дахно Григорий Сергеевич ¹
Малышев Дмитрий Сергеевич ^1,2
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
2. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
е-mail: dahnogrigory@yandex.ru, dsmalyshev@rambler.ru

Статья поступила 29 мая 2022 г.
После доработки — 23 октября 2022 г.
Принята к публикации 24 октября 2022 г.

Литература

[1] Alekseev V. E., Korobitsyn D. V., Lozin V. V. Boundary classes of graphs for the dominating set problem // Discrete Math. 2004. V. 285, No. 1–3. P. 1–6.

[2] Malyshev D. S. A complexity dichotomy and a new boundary class for the dominating set problem // J. Comb. Optim. 2016. V. 32. P. 226–243.

[3] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. 2003. V. 132, No. 1–3. P. 17–26.

[4] Alekseev V. E., Boliac R., Korobitsyn D. V., Lozin V. V. NP-hard graph problems and boundary classes of graphs // Theor. Comput. Sci. 2007. V. 389, No. 1–2. P. 219–236.

[5] Коробицын Д. В. О сложности определения числа доминирования в моногенных классах графов // Дискрет. математика. 1990. Т. 2, № 3. С. 90–96.

[6] Malyshev D. S. A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs // Discrete Appl. Math. 2016. V. 203. P. 117–126.

[7] Malyshev D. S., Pardalos P. M. Critical hereditary graph classes: A survey // Optim. Lett. 2016. V. 10, No. 8. P. 1593–1612.

[8] Малышев Д. C. Континуальные множества граничных классов графов для задач о раскраске // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 5. С. 41–51.

[9] Малышев Д. C. Критические классы графов для задачи о рёберном списковом ранжировании // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 6. С. 59–76.

[10] Murphy O. J. Computing independent sets in graphs with large girth // Discrete Appl. Math. 1992. V. 35, No. 2. P. 167–170.

[11] Müller H., Brandstädt A. The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs // Theor. Comput. Sci. 1987. V. 53, No. 2–3. P. 257–265.

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