Abstract
An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as \(P_4\)-free graphs or \(2K_2\)-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating difficult instances of the problem from polynomially solvable ones consists of the so called boundary classes. However, none of such classes has been identified so far for the upper dominating set problem. In the present paper, we discover the first boundary class for this problem.
V. Lozin—The author gratefully acknowledges support from EPSRC, grant EP/L020408/1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
AbouEisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B.: A dichotomy for upper domination in monogenic classes. In: Zhang, Z., Wu, L., Xu, W., Du, D.-Z. (eds.) COCOA 2014. LNCS, vol. 8881, pp. 258–267. Springer, Heidelberg (2014)
Alekseev, V.E.: On easy and hard hereditary classes of graphs with respect to the independent set problem. Discrete Appl. Math. 132, 17–26 (2003)
Alekseev, V.E., Korobitsyn, D.V., Lozin, V.V.: Boundary classes of graphs for the dominating set problem. Discrete Math. 285, 1–6 (2004)
Alekseev, V.E., Boliac, R., Korobitsyn, D.V., Lozin, V.V.: NP-hard graph problems and boundary classes of graphs. Theor. Comput. Sci. 389, 219–236 (2007)
Cheston, G.A., Fricke, G., Hedetniemi, S.T., Jacobs, D.P.: On the computational complexity of upper fractional domination. Discrete Appl. Math. 27(3), 195–207 (1990)
Cockayne, E.J., Favaron, O., Payan, C., Thomason, A.G.: Contributions to the theory of domination, independence and irredundance in graphs. Discrete Math. 33(3), 249–258 (1981)
Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theor. Comput. Syst. 33(2), 125–150 (2000)
Courcelle, B., Olariu, S.: Upper bounds to the clique-width of a graph. Discrete Appl. Math. 101, 77–114 (2000)
Hare, E.O., Hedetniemi, S.T., Laskar, R.C., Peters, K., Wimer, T.: Linear-time computability of combinatorial problems on generalized-series-parallel graphs. In: Johnson, D.S., et al. (eds.) Discrete Algorithms and Complexity, pp. 437–457. Academic Press, New York (1987)
Jacobson, M.S., Peters, K.: Chordal graphs and upper irredundance, upper domination and independence. Discrete Math. 86(1–3), 59–69 (1990)
Kamiński, M., Lozin, V., Milanič, M.: Recent developments on graphs of bounded clique-width. Discrete Appl. Math. 157, 2747–2761 (2009)
Korobitsyn, D.V.: On the complexity of determining the domination number in monogenic classes of graphs. Diskretnaya Matematika 2(3), 90–96 (1990). (in Russian, translation in Discrete Math. Appl. 2(2), 191–199 (1992))
Korpelainen, N., Lozin, V.V., Malyshev, D.S., Tiskin, A.: Boundary properties of graphs for algorithmic graph problems. Theor. Comput. Sci. 412, 3545–3554 (2011)
Korpelainen, N., Lozin, V., Razgon, I.: Boundary properties of well-quasi-ordered sets of graphs. Order 30, 723–735 (2013)
Lozin, V.V.: Boundary classes of planar graphs. Comb. Probab. Comput. 17, 287–295 (2008)
Lozin, V., Milanič, M.: Critical properties of graphs of bounded clique-width. Discrete Math. 313, 1035–1044 (2013)
Lozin, V., Purcell, C.: Boundary properties of the satisfiability problems. Inf. Process. Lett. 113, 313–317 (2013)
Lozin, V., Rautenbach, D.: On the band-, tree- and clique-width of graphs with bounded vertex degree. SIAM J. Discrete Math. 18, 195–206 (2004)
Lozin, V., Zamaraev, V.: Boundary properties of factorial classes of graphs. J. Graph Theor. 78, 207–218 (2015)
Murphy, O.J.: Computing independent sets in graphs with large girth. Discrete Appl. Math. 35, 167–170 (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
AbouEisha, H., Hussain, S., Lozin, V., Monnot, J., Ries, B., Zamaraev, V. (2016). A Boundary Property for Upper Domination. In: Mäkinen, V., Puglisi, S., Salmela, L. (eds) Combinatorial Algorithms. IWOCA 2016. Lecture Notes in Computer Science(), vol 9843. Springer, Cham. https://doi.org/10.1007/978-3-319-44543-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-44543-4_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44542-7
Online ISBN: 978-3-319-44543-4
eBook Packages: Computer ScienceComputer Science (R0)