Abstract
We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.
Similar content being viewed by others
References
AbouEisha H, Hussain S, Lozin V, Monnot J, Ries B (2014) A dichotomy for upper domination in monogenic classes. In: Combinatorial optimization and applications. Lecture notes in computer science, vol 8881. Springer, pp 258–267
Alekseev V (1983) On the local restrictions effect on the complexity of finding the graph independence number. In: Combinatorial-algebraic methods in applied mathematics. Gorkiy University Press, Gorkiy, pp 3–13 [in russian]
Alekseev V (1999) A polynomial algorithm for finding the largest independent sets in fork-free graphs. Diskretn Analiz i Issled Oper Ser 1 6(4):3–19 [in russian]
Alekseev V (2003) On easy and hard hereditary classes of graphs with respect to the independent set problem. Discret Appl Math 132(1–3):17–26
Alekseev V, Boliac R, Korobitsyn D, Lozin V (2007) NP-hard graph problems and boundary classes of graphs. Theor Comput Sci 389(1–2):219–236
Alekseev V, Korobitsyn D, Lozin V (2004) Boundary classes of graphs for the dominating set problem. Discret Math 285(1–3):1–6
Bacsó G, Tuza Z (1990) Dominating cliques in \(P_5\)-free graphs. Period Math Hung 21:303–308
Bertossi A (1984) Dominating sets for split and bipartite graphs. Inform Process Lett 19(1):37–40
Brandstädt A, Dragan F, Le H-O, Mosca R (2005) New graph classes of bounded clique-width. Theory Comput Syst 38(5):623–645
Broersma H, Golovach P, Paulusma D, Song J (2012) Updating the complexity status of coloring graphs without a fixed induced linear forest. Theor Comput Sci 414(1):9–19
Clark B, Colbourn C, Johnson D (1990) Unit disk graphs. Ann Discret Math 48:165–177
Courcelle B, Makowsky J, Rotics U (2000) Linear time optimization problems on graphs of bounded clique width. Theory Comput Syst 33(2):125–150
Garey M, Johnson D (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, New York 1979
Golovach P, Paulusma D (2014) List coloring in the absence of two subgraphs. Discret Appl Math 166:123–130
Golovach P, Paulusma D, Ries B (2015) Coloring graphs characterized by a forbidden subgraph. Discret Appl Math 180(1):101–110
Golovach P, Paulusma D, Song J (2013) 4-coloring \(H\)-free graphs when \(H\) is small. Discret Appl Math 161(1–2):140–150
Graphs: 5-vertices. Information system on graph classes and their inclusions. http://www.graphclasses.org/smallgraphs.html#nodes5. Accessed 27 Jan 2015
Graphclass: AT-free. Information system on graph classes and their inclusions. http://www.graphclasses.org/classes/gc_61.html. Accessed 27 Jan 2015
Korobitsyn D (1992) On the complexity of domination number determination in monogenic classes of graphs. Discret Math Appl 2(2):191–199
Kral’ D, Kratochvil J, Tuza Z, Woeginger G (2001) Complexity of coloring graphs without forbidden induced subgraphs. Lect. Notes Comput Sci 2204:254–262
Kratsch D (2000) Domination and total domination in asteroidal triple-free graphs. Discret Appl Math 99(1–3):111–123
Kratsch S, Schweitzer P (2012) Graph isomorphism for graph classes characterized by two forbidden induced subgraphs. Lect Notes Comput Sci 7551:34–45
Lokshtantov D, Vatshelle M, Villanger Y (2014) Independent set in \(P_5\)-free graphs in polynomial time. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp 570–581
Lozin V (2008) Boundary classes of planar graphs. Comb Probab Comput 17(2):287–295
Lozin V, Malyshev D (2015) Vertex coloring of graphs with few obstructions. Discret Appl Math. doi:10.1016/j.dam.2015.02.015
Lozin V, Mosca R (2004) Independent sets in extensions of \(2K_2\)-free graphs. Discret Appl Math 146(1): 74–80
Malyshev D (2013) The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs. Discret Math (submitted)
Malyshev D (2014) The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices. Sib Electron Math Rep 11:811–822
Malyshev D (2014) Classes of graphs critical for the edge list-ranking problem. J Appl Ind Math 8(2): 245–255
Problem: Domination. Information system on graph classes and their inclusions. http://www.graphclasses.org/classes/problem_Domination.html. Accessed 27 Jan 2015
Schweitzer P (2014) Towards an isomorphism dichotomy for hereditary graph classes. arXiv, arXiv:1411.1977
Yannakakis M, Gavril F (1980) Edge dominating sets in graphs. SIAM J Appl Math 38(3):364–372
Zverovich I (2003) The domination number of \((K_p, P_5)\)-free graphs. Australas J Comb 27:95–100
Acknowledgments
The article was prepared within the framework of the Academic Fund Program at the National Research University Higher School of Economics (HSE) in 2015–2016 (Grant 15-01-0010) and supported within the framework of a subsidy granted to the HSE by the Government of the Russian Federation for the implementation of the Global Competitiveness Program.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Malyshev, D.S. A complexity dichotomy and a new boundary class for the dominating set problem. J Comb Optim 32, 226–243 (2016). https://doi.org/10.1007/s10878-015-9872-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9872-z