Abstract
Let \(G=(V,E)\) be an undirected graph. A minus dominating function for G is a function \(f:V \rightarrow \{-1, 0,+1\}\) such that for each vertex \(v \in V\), the sum of the function values over the closed neighborhood of v is positive. The weight of a minus dominating function f for G, denoted by w(f(V)), is \(\sum f(v)\) over all vertices \(v \in V\). The minus domination (MD) number of G is the minimum weight for any minus dominating function for G. The minus domination (MD) problem asks for the minus dominating function which contributes the MD number. In this paper, we first show that the MD problem is W[2]-hard for general graphs. Then we show that the MD problem is NP-complete for subcubic bipartite planar graphs. We further show that the MD problem is APX-hard for graphs of maximum degree seven. Lastly, we present the first fixed-parameter algorithm for the MD problem on subcubic graphs, which runs in \(O^{*}(2.3761^{5k})\) time, where k is the MD number of the graph.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Proc. 3rd Italian Conference on Algorithms and Complexity (CIAC), pp. 288–298 (1997)
Damaschke, P.: Minus domination in small-degree graphs. Discrete Applied Mathematics 108(1–2), 53–64 (2001)
Downey, R.G., Fellows, M.R.: Parameterized Complexity, 3rd edn. Springer (1999)
Dunbar, J., Goddard, W., Hedetniemi, S., McRae, A., Henning, M.A.: The algorithmic complexity of minus domination in graphs. Discrete Applied Mathematics 68(1–2), 73–84 (1996)
Dunbar, J., Hedetniemi, S., McRae, A., Henning, M.A.: Minus domination in graphs. Discrete Applied Mathematics 199(1–3), 35–47 (1999)
Faria, L., Hon, W.-K., Kloks, T., Liu, H.-H., Wang, T.-M., Wang, Y.-L.: On complexities of minus domination. In: Widmayer, P., Xu, Y., Zhu, B. (eds.) COCOA 2013. LNCS, vol. 8287, pp. 178–189. Springer, Heidelberg (2013)
Lichtenstein, D.: Planar formulae and their uses. SIAM Journal on Computing 11(2), 329–343 (1982)
Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences 43(3), 425–440 (1991)
Zheng, Y., Wang, J., Feng, Q., Chen, J.: FPT results for signed domination. In: Agrawal, M., Cooper, S.B., Li, A. (eds.) TAMC 2012. LNCS, vol. 7287, pp. 572–583. Springer, Heidelberg (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Lin, JY., Liu, CH., Poon, SH. (2015). Algorithmic Aspect of Minus Domination on Small-Degree Graphs. In: Xu, D., Du, D., Du, D. (eds) Computing and Combinatorics. COCOON 2015. Lecture Notes in Computer Science(), vol 9198. Springer, Cham. https://doi.org/10.1007/978-3-319-21398-9_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-21398-9_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-21397-2
Online ISBN: 978-3-319-21398-9
eBook Packages: Computer ScienceComputer Science (R0)