Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
Volume 30, No 1, 2023, P. 28-39
UDC 519.17
G. S. Dakhno and D. S. Malyshev
On a countable family of boundary graph classes for the dominating set problem
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.
Keywords: hereditary graph class, computational complexity, dominating set.
DOI: 10.33048/daio.2023.30.742
Grigory S. Dakhno 1
Dmitry S. Malyshev 1,2
1. National Research University “Higher School of Economics”,
25/12 Bolshaya Pechyorskaya Street, 603155 Nizhny Novgorod, Russia
2. Lobachevsky Nizhny Novgorod University,
23 Gagarin Avenue, 603950 Nizhniy Novgorod, Russia
e-mail: dahnogrigory@yandex.ru, dsmalyshev@rambler.ru
Received May 29, 2022
Revised October 23, 2022
Accepted October 24, 2022
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).
