Abstract
This paper studies Upper Domination, i.e., the problem of computing the maximum cardinality of a minimal dominating set in a graph, with a focus on parameterised complexity. Our main results include W[1]-hardness for Upper Domination, contrasting FPT membership for the parameterised dual Co-Upper Domination. The study of structural properties also yields some insight into Upper Total Domination. We further consider graphs of bounded degree and derive upper and lower bounds for kernelisation.
C. Bazgan—Institut Universitaire de France.
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
Abu-Khzam, F.N., Bazgan, C., Chopin, M., Fernau, H.: Data reductions and combinatorial bounds for improved approximation algorithms. J. Comput. Syst. Sci. 82(3), 503–520 (2016)
Binkele-Raible, D., Brankovic, L., Cygan, M., Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Pilipczuk, M., Rossmanith, P., Wojtaszczyk, J.O.: Breaking the \(2^n\)-barrier for irredundance: two lines of attack. J. Discrete Algorithms 9, 214–230 (2011)
Brankovic, L., Fernau, H.: A novel parameterised approximation algorithm for minimum vertex cover. Theor. Comput. Sci. 511, 85–108 (2013)
Cesati, M.: The turing way to parameterized complexity. J. Comput. Syst. Sci. 67, 654–685 (2003)
Chen, J., Fernau, H., Kanj, I.A., Xia, G.: Parametric duality and kernelization: lower bounds and upper bounds on kernel size. SIAM J. Comput. 37, 1077–1108 (2007)
Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40–42), 3736–3756 (2010)
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)
Cygan, M., Fomin, F., Kowalik, Ł., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Switzerland (2015)
Downey, R.G., Fellows, M.R.: Fixed parameter tractability and completeness. Congressus Numerantium 87, 161–187 (1992)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)
Downey, R.G., Fellows, M.R., Raman, V.: The complexity of irredundant set parameterized by size. Discrete Appl. Math. 100, 155–167 (2000)
Fang, Q.: On the computational complexity of upper total domination. Discrete Appl. Math. 136(1), 13–22 (2004)
Fellows, M.R., Hermelin, D., Rosamond, F., Vialette, S.: On the parameterized complexity of multiple-interval graph problems. Theor. Comput. Sci. 410(1), 53–61 (2009)
Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A.: Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. ACM Trans. Algorithms 5(1), 1–17 (2008)
Fomin, F.V., Høie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97, 191–196 (2006)
Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, vol. 208. Marcel Dekker, New York (1998)
Hennings, M., Yeo, A.: Total Domination in Graphs. Springer, New York (2013)
Iwata, Y.: A faster algorithm for dominating set analyzed by the potential method. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol. 7112, pp. 41–54. Springer, Heidelberg (2012)
Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: Kannan, R., Narayan Kumar, K. (eds.) IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. LIPIcs, FSTTCS 2009, vol. 4, pp. 287–298. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
Pietrzak, K.: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. J. Comput. Syst. Sci. 67(4), 757–771 (2003)
van Rooij, J.M.M., Bodlaender, H.L.: Exact algorithms for dominating set. Discrete Appl. Math. 159(17), 2147–2164 (2011)
Acknowledgements
We thank our colleagues Serge Gaspers, David Manlove and Daniel Meister for some discussions on (total) upper domination. Part of this research was supported by Deutsche Forschungsgemeinschaft, grant FE 560/6-1.
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
Bazgan, C. et al. (2016). Algorithmic Aspects of Upper Domination: A Parameterised Perspective. In: Dondi, R., Fertin, G., Mauri, G. (eds) Algorithmic Aspects in Information and Management. AAIM 2016. Lecture Notes in Computer Science(), vol 9778. Springer, Cham. https://doi.org/10.1007/978-3-319-41168-2_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-41168-2_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-41167-5
Online ISBN: 978-3-319-41168-2
eBook Packages: Computer ScienceComputer Science (R0)