Abstract
A mixed domination of a graph \(G = (V, E)\) is a mixed set D of vertices and edges such that for every edge or vertex, if it is not in D, then it is adjacent or incident to at least one vertex or edge in D. The Mixed Domination problem is to check whether there is a mixed domination of size at most k in a graph. Mixed domination is a mixture concept of vertex domination and edge domination, and the mixed domination problem has been studied from the view of approximation algorithms, parameterized algorithms, and so on. In this paper, we give a branch-and-search algorithm with running time bound of \(O^*(4.172^k)\), which improves the previous bound of \(O^*(7.465^k)\). For kernelization, it is known that the problem parameterized by k in general graphs is unlikely to have a polynomial kernel. We show the problem in planar graphs allows linear kernels by giving a kernel of 11k vertices.
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
Alavi, Y., Behzad, M., Lesniak-Foster, L.M., Nordhaus, E.: Total matchings and total coverings of graphs. J. Graph Theory 1(2), 135–140 (1977)
Fernau, H.: edge dominating set: efficient enumeration-based exact algorithms. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 142–153. Springer, Heidelberg (2006). https://doi.org/10.1007/11847250_13
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16533-7
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
Hatami, P.: An approximation algorithm for the total covering problem. Discussiones Mathematicae Graph Theory 27(3), 553–558 (2007)
Hedetniemi, S.M., Hedetniemi, S.T., Laskar, R., McRae, A., Majumdar, A.: Domination, independence and irredundance in total graphs: a brief survey. In: Graph Theory, Combinatorics and Applications: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs, vol. 2, pp. 671–683. Wiley, New York (1995)
Jain, P., Jayakrishnan, M., Panolan, F., Sahu, A.: Mixed Dominating Set: a parameterized perspective. In: Bodlaender, H.L., Woeginger, G.J. (eds.) WG 2017. LNCS, vol. 10520, pp. 330–343. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68705-6_25
Lan, J.K., Chang, G.J.: On the mixed domination problem in graphs. Theoret. Comput. Sci. 476, 84–93 (2013)
Manlove, D.F.: On the algorithmic complexity of twelve covering and independence parameters of graphs. Discrete Appl. Math. 91(1–3), 155–175 (1999)
Rajaati, M., Hooshmandasl, M.R., Dinneen, M.J., Shakiba, A.: On fixed-parameter tractability of the mixed domination problem for graphs with bounded tree-width. Discrete Math. Theoret. Comput. Sci. 20(2), 1–25 (2018)
Xiao, M.: Upper and lower bounds on approximating weighted mixed domination. In: COCOON 2019 (2019, to appear)
Xiao, M., Kloks, T., Poon, S.H.: New parameterized algorithms for the edge dominating set problem. Theoret. Comput. Sci. 511, 147–158 (2013)
Zhao, Y., Kang, L., Sohn, M.Y.: The algorithmic complexity of mixed domination in graphs. Theoret. Comput. Sci. 412(22), 2387–2392 (2011)
Acknowledgements
This work was supported by the National Natural Science Foundation of China, under grants 61772115 and 61370071.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Xiao, M., Sheng, Z. (2019). Improved Parameterized Algorithms for Mixed Domination. In: Du, DZ., Li, L., Sun, X., Zhang, J. (eds) Algorithmic Aspects in Information and Management. AAIM 2019. Lecture Notes in Computer Science(), vol 11640. Springer, Cham. https://doi.org/10.1007/978-3-030-27195-4_28
Download citation
DOI: https://doi.org/10.1007/978-3-030-27195-4_28
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-27194-7
Online ISBN: 978-3-030-27195-4
eBook Packages: Computer ScienceComputer Science (R0)