О счетном семействе граничных классов графов для задачи о доминирующем множестве

О счетном семействе граничных классов графов для задачи о доминирующем множестве

Дахно Г. С., Малышев Д. С.
Дискретный анализ и исследование операций, 30, 1, 28-39 (2023)
Скачать статью

УДК 519.17 
DOI: 10.33048/daio.2023.30.742

Аннотация:

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

Литература:
  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.

Исследование выполнено в рамках Программы фундаментальных исследований Национального исследовательского университета «Высшая школа экономики».

Дахно Григорий Сергеевич
  1. Национальный исследовательский университет «Высшая школа экономики», 
    ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия

E-mail: dahnogrigory@yandex.ru

 

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

E-mail: dsmalyshev@rambler.ru

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

Abstract:

The hereditary class is a set of simple graphs closed under deletion of vertices; every such class is defined by the set of its minimal forbidden induced subgraphs. If this set is finite, then it is called finitely defined. The concept of a boundary class is a useful tool for analysis of the computational complexity of graph problems in the finitely defined classes family. The dominating set problem for a given graph is to determine whether it has a given-size subset of vertices such that every vertex outside the subset has at least one neighbor in the subset. Previously, exactly 4 boundary classes were known for this problem (if $\mathbb {P} \ne \mathbb {NP}$). This work considers some countable set of concrete classes of graphs and proves that each its element is a boundary class for the dominating set problem (if $\mathbb {P} \ne \mathbb {NP}$). We also prove $\mathbb {NP}$-completeness of this problem for graphs that contain neither induced 6-path nor induced 4-clique, which means that the set of known boundary classes for the dominating set problem is not complete (if $\mathbb {P} \ne \mathbb {NP}$). 
Bibliogr. 11.

References:
  1. V. E. Alekseev, D. V. Korobitsyn, and V. V. Lozin, Boundary classes of graphs for the dominating set problem, Discrete Math. 285 (1–3) 1–6 (2004).
     
  2. D. S. Malyshev, A complexity dichotomy and a new boundary class for the dominating set problem, J. Comb. Optim. 32, 226–243 (2016).
     
  3. V. E. Alekseev, On easy and hard hereditary classes of graphs with respect to the independent set problem, Discrete Appl. Math. 132 (1–3), 17–26 (2003).
     
  4. V. E. Alekseev, R. Boliac, D. V. Korobitsyn, andV. V. Lozin, NP-hard graph problems and boundary classes of graphs, Theor. Comput. Sci. 389 (1–2), 219–236 (2007).
     
  5. D. V. Korobitsyn, Complexity of some problems on hereditary classes of graphs, Diskretn. Mat. 2 (3), 90–96 (1990) [Russian] [Discrete Math. Appl. 2 (2), 191–199 (1992)].
     
  6. D. S. Malyshev, A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, Discrete Appl. Math. 203, 117–126 (2016).
     
  7. D. S. Malyshev and P. M. Pardalos, Critical hereditary graph classes: A survey, Optim. Lett. 10 (8), 1593–1612 (2016).
     
  8. D. S. Malyshev, Continued sets of boundary classes of graphs for colorability problems, Diskretn. Anal. Issled. Oper. 16 (5), 41–51 (2009) [Russian].
     
  9. D. S. Malyshev, Critical graph classes for the edge list-ranking problem, Diskretn. Anal. Issled. Oper. 20 (6), 59–76 (2013) [Russian] [J. Appl. Industr. Math. 8 (2), 245–255 (2014)].
     
  10. O. J. Murphy, Computing independent sets in graphs with large girth, Discrete Appl. Math. 35 (2), 167–170 (1992).
     
  11. H. Müller and A. Brandstädt, The NP-completeness of Steiner tree and dominating set for chordal bipartite graphs, Theor. Comput. Sci. 53 (2–3), 257–265 (1987).