×

On complexities of minus domination. (English) Zbl 1387.90264

Summary: A function \(f:V\rightarrow\{-1,0,1\}\) is a minus-domination function of a graph \(G=(V,E)\) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of \(f\) is the sum of \(f(x)\) over all vertices \(x\in V\). In the minus-domination problem, one tries to minimize the weight of a minus-domination function. In this paper, we show that (1) the minus-domination problem is fixed-parameter tractable for \(d\)-degenerate graphs when parameterized by the size of the minus-dominating set and by \(d\), where the size of a minus domination is the number of vertices that are assigned \(1\), (2) the minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs, (3) it is NP-complete for split graphs, and (4) there is no fixed-parameter algorithm for minus-domination.

MSC:

90C35 Programming involving graphs or networks
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
90C60 Abstract computational complexity for mathematical programming problems
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Gutner, S., Linear time algorithms for finding a dominating set of fixed size in degenerated graphs, Algorithmica, 54, 544-556 (2009) · Zbl 1192.68464
[2] Fomin, F.; Lokshtanov, D.; Saurabh, S.; Thilikos, D., Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs, (Proceedings STACS’13. Proceedings STACS’13, LPIcs, vol. 20 (2013), Schloss Dagstuhl-Leibniz-Zentrum für Informatik), 92-103 · Zbl 1354.68120
[3] Damaschke, P., Minus domination in small-degree graphs, Discrete Appl. Math., 108, 53-64 (2001) · Zbl 0971.05086
[4] Dunbar, J.; Goddard, W.; Hedetniemi, S.; Henning, M.; McRae, A., The algorithmic complexity of minus domination in graphs, Discrete Appl. Math., 68, 73-84 (1996) · Zbl 0848.05041
[5] Dunbar, J.; Hedetniemi, S.; Henning, M. A.; McRae, A., Minus domination in graphs, Discrete Math., 199, 35-47 (1999) · Zbl 0928.05046
[6] Kim, H. K., The lower bound of minus domination number in some special graphs, Korean J. Math. Sci., 10, 21-24 (2003)
[7] Liu, H.; Sun, L., On the minus domination number of graphs, Czechoslovak Math. J., 54, 883-887 (2004) · Zbl 1080.05523
[8] Zelinka, B., Signed and minus domination in bipartite graphs, Czechoslovak Math. J., 56, 587-590 (2006) · Zbl 1164.05428
[9] Shan, E.; Cheng, T. C.E., Remarks on the minus (signed) total domination in graphs, Discrete Math., 308, 3373-3380 (2008) · Zbl 1169.05367
[10] Chen, Y.; Cheng, T. C.E.; Ng, C. T.; Shan, E., A note on domination and minus domination numbers in cubic graphs, Appl. Math. Lett., 18, 1062-1067 (2005) · Zbl 1082.05067
[11] Shang, W.; Yuan, J., Upper minus domination in a claw-free cubic graph, Discrete Math., 306, 2983-2988 (2006) · Zbl 1106.05072
[12] Yang, X.; Hou, Q.; Huang, X.; Xuan, H., The difference between the domination number and minus domination number of a cubic graph, Appl. Math. Lett., 16, 1089-1093 (2003) · Zbl 1043.05092
[13] Matoušek, J., Lower bound on the minus-domination number, Discrete Math., 233, 361-370 (2001) · Zbl 0986.05081
[14] Xu, B. G., On minus domination and signed domination in graphs, J. Math. Res. Exposition, 23, 586-590 (2003) · Zbl 1049.05061
[15] Lua, C. L.; Peng, S. L.; Tang, C. Y., Efficient minus and signed domination in graphs, Theoret. Comput. Sci., 301, 381-397 (2003) · Zbl 1022.68103
[16] Lee, C.; Chang, M., Variations of \(Y\)-dominating functions on graphs, Discrete Math., 308, 4185-4204 (2008) · Zbl 1169.05037
[17] Zheng, Y.; Wang, J.; Feng, Q., Kernelization and lowerbounds of the signed domination problem, (Proceedings FAW-AAIM’13. Proceedings FAW-AAIM’13, LNCS, vol. 7924 (2013), Springer-Verlag), 261-271 · Zbl 1303.05148
[18] Fernau, H.; Rodríguez-Velázquez, J., A survey on alliances and related parameters in graphs, Electron. J. Graph Theory Appl., 2, 70-86 (2014) · Zbl 1306.05180
[19] Bodlaender, H.; Lokshtanov, D.; Penninkx, E., Planar capacitated dominating set is \(W [1]\)-hard, (Proceedings of the Workshop on Parameterized and Exact Computation. Proceedings of the Workshop on Parameterized and Exact Computation, LNCS, vol. 5917 (2009), Springer-Verlag), 50-60 · Zbl 1273.68145
[20] Thomason, A., The extremal function for complete minors, J. Combin. Theory Ser. B, 81, 318-338 (2001) · Zbl 1024.05083
[21] Alber, J.; Fan, H.; Fellows, M. R.; Fernau, H.; Niedermeier, R.; Rosamond, F.; Stege, U., A refined search tree technique for dominating set on planar graphs, J. Comput. System Sci., 71, 385-405 (2005) · Zbl 1101.68712
[22] Langer, A.; Rossmanith, P.; Sikdar, S., Linear-time algorithms for graphs of bounded rankwidth: A fresh look using game theory, (Proceedings TAMC’11. Proceedings TAMC’11, LNCS, vol. 6648 (2011), Springer-Verlag), 505-516 · Zbl 1331.68111
[23] Yeh, H.; Chang, G., Algorithmic aspects of majority domination, Taiwanese J. Math., 1, 343-350 (1997) · Zbl 0882.05114
[26] Howorka, E., A characterization of distance-hereditary graphs, Q. J. Math., 28, 7-420 (1977) · Zbl 0376.05040
[27] Chang, M.; Hsieh, S.; Chen, G., Dynamic programming on distance-hereditary graphs, (Proceedings 8th ISAAC’97. Proceedings 8th ISAAC’97, LNCS, vol. 1350 (1997), Springer-Verlag), 344-353
[28] Cunningham, W.; Edmonds, J., A combinatorial decomposition theory, Canad. J. Math., 32, 734-765 (1980) · Zbl 0442.05054
[29] Charbit, P.; de Montgolfier, F.; Raffinot, M., Linear time split decomposition revisited, SIAM J. Discrete Math., 26, 499-514 (2012) · Zbl 1248.68369
[30] Cunningham, W., Decomposition of directed graphs, SIAM J. Algebr. Discrete Methods, 3, 214-228 (1982) · Zbl 0497.05031
[31] Gioan, E.; Paul, C.; Tedder, M.; Corneil, D., Practical and efficient split decompositionb via graph labelled trees, Algorithmica, 55, 789-843 (2014) · Zbl 1303.05191
[32] Hliněný, P.; Oum, S., Finding branch-decompositions and rank-decompositions, (Proceedings ESA’07. Proceedings ESA’07, LNCS, vol. 4698 (2007), Springer-Verlag), 163-174 · Zbl 1151.05046
[33] Farber, M., Domination, independent domination, and duality in strongly chordal graphs, Discrete Appl. Math., 7, 115-130 (1984) · Zbl 0531.05045
[35] Scheinerman, E.; Ullman, D., Fractional Graph Theory (1997), Wiley
[36] Fulkerson, D.; Hoffman, A.; Oppenheim, R., On balanced matrices, Math. Program. Stud., 1, 120-132 (1974) · Zbl 0357.90038
[37] Hoffman, A.; Kolen, A.; Sakarovitch, M., Totally-balanced and greedy matrices, SIAM J. Algebr. Discrete Methods, 6, 721-730 (1985) · Zbl 0573.05041
[38] Kolen, A., Location problems on trees and in the rectilinear plane (1982), Mathematisch Centrum: Mathematisch Centrum Amsterdam, (Ph.D. thesis)
[39] Lubiw, A., \( \Gamma \)-Free matrices (1982), University of Waterloo: University of Waterloo Canada, (Master’s Thesis)
[41] Mellor, A.; Prieto, E.; Mathieson, L.; Moscato, P., A kernelisation approach for multiple \(d\)-hitting set and its application in optimal multi-drug therapeutic combinations, PLoS ONE, 5, e13055 (2010)
[42] Hattingh, J.; Henning, M.; Slater, P., The algorithmic complexity of signed domination in graphs, Australas. J. Combin., 12, 101-112 (1995) · Zbl 0835.68089
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.