Geodesic
The Complexity of Secure Domination Problem in Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 385-396.

Voir la notice de l'article provenant de la source Library of Science

A dominating set of a graph G is a subset D ⊆ V (G) such that every vertex not in D is adjacent to at least one vertex in D. A dominating set S of G is called a secure dominating set if each vertex u ∈ V (G) S has one neighbor v in S such that (S v) ∪ u is a dominating set of G. The secure domination problem is to determine a minimum secure dominating set of G. In this paper, we first show that the decision version of the secure domination problem is NP-complete for star convex bipartite graphs and doubly chordal graphs. We also prove that the secure domination problem cannot be approximated within a factor of (1−ε) ln |V | for any ε gt; 0, unless NP⊆DTIME (|V |O(log log |V|)). Finally, we show that the secure domination problem is APX-complete for bounded degree graphs.
Keywords: secure domination, star convex bipartite graph, doubly chordal graph, NP-complete, APX-complete 
@article{DMGT_2018_38_2_a3,
     author = {Wang, Haichao and Zhao, Yancai and Deng, Yunping},
     title = {The {Complexity} of {Secure} {Domination} {Problem} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {385--396},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/}
}
TY  - JOUR
AU  - Wang, Haichao
AU  - Zhao, Yancai
AU  - Deng, Yunping
TI  - The Complexity of Secure Domination Problem in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 385
EP  - 396
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/
LA  - en
ID  - DMGT_2018_38_2_a3
ER  - 
%0 Journal Article
%A Wang, Haichao
%A Zhao, Yancai
%A Deng, Yunping
%T The Complexity of Secure Domination Problem in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 385-396
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/
%G en
%F DMGT_2018_38_2_a3
Wang, Haichao; Zhao, Yancai; Deng, Yunping. The Complexity of Secure Domination Problem in Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 2, pp. 385-396. http://geodesic.mathdoc.fr/item/DMGT_2018_38_2_a3/

[1] P. Alimonti and V. Kann, Some APX-completeness results for cubic graphs, Theoret. Comput. Sci. 237 (2000) 123–134. doi:10.1016/S0304-3975(98)00158-3

[2] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela and M. Protasi, Complexity and Approximation (Springer, Berlin, 1999). doi:10.1007/978-3-642-58412-1

[3] A.A. Bertossi, Dominating sets for split and bipartite graphs, Inform. Process. Lett. 19 (1984) 37–40. doi:10.1016/0020-0190(84)90126-1

[4] A. Brandstädt, F.F. Dragan, V. Chepoi and V. Voloshin, Dually chordal graphs, SIAM J. Discrete Math. 11 (1998) 437–455. doi:10.1137/S0895480193253415

[5] A.P. Burger, M.A. Henning and J.H. van Vuuren, Vertex covers and secure domination in graphs, Quaest. Math. 31 (2008) 163–171. doi:10.2989/QM.2008.31.2.5.477

[6] A.P. Burger, A.P. de Villiers and J.H. van Vuuren, A linear algorithm for secure domination in trees, Discrete Appl. Math. 171 (2014) 15–27. doi:0.1016/j.dam.2014.02.001

[7] A.P. Burger, A.P. de Villiers and J.H. van Vuuren, Edge criticality in secure graph domination, Discrete Optim. 18 (2015) 111–122. doi:10.1016/j.disopt.2015.08.001

[8] M. Chlebík and J. Chlebíková, Approximation hardness of dominating set problems in bounded degree graphs, Inform. and Comput. 206 (2008) 1264–1275. doi:10.1016/j.ic.2008.07.003

[9] E.J. Cockayne, Irredundance, secure domination and maximum degree in trees, Discrete Math. 307 (2007) 12–17. doi:10.1016/j.disc.2006.05.037

[10] E.J. Cockayne, P.J.P. Grobler,W.R. Gründlingh, J. Munganga and J.H. van Vuuren, Protection of a graph, Util. Math. 67 (2005) 19–32.

[11] D.R. Fulkerson and O.A. Gross, Incidence matrices and interval graphs, Pacific J. Math. 15 (1965) 835–855. doi:10.2140/pjm.1965.15.835

[12] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, San Francisco, 1979).

[13] P.J.P. Grobler and C.M. Mynhardt, Secure domination critical graphs, Discrete Math. 309 (2009) 5820–5827. doi:10.1016/j.disc.2008.05.050

[14] F. Harary and T.W. Haynes, Double domination in graphs, Ars Combin. 55 (2000) 201–213.

[15] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, New York, 1998).

[16] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998).

[17] W. Jiang, T. Liu, T. Ren and K. Xu, Two hardness results on feedback vertex sets, in: Proc. Fronties in Algorithmics and Algorytmic Aspects in Information and Managment, M. Atallah, X.Y. Li and B. Zhu (Ed(s)), Lecture Notes in Comput. Sci. 6681 (2011) 233–243. doi:10.1007/978-3-642-21204-826

[18] R. Klasing and C. Laforest, Hardness results and approximation algorithms of k-tuple domination in graphs, Inform. Process. Lett. 89 (2004) 75–83. doi:10.1016/j.ipl.2003.10.004

[19] W.F. Klostermeyer and C.M. Mynhardt, Secure domination and secure total domination in graphs, Discuss. Math. Graph Theory 28 (2008) 267–284. doi:10.7151/dmgt.1405

[20] H.B. Merouane and M. Chellali, On secure domination in graphs, Inform. Process. Lett. 115 (2015) 786–790. doi:10.1016/j.ipl.2015.05.006

[21] C.M. Mynhardt, H.C. Swart and L. Ungerer, Excellent trees and secure domination, Util. Math. 67 (2005) 255–267.

[22] C.H. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes, J. Comput. System Sci. 43 (1991) 425–440. doi:10.1016/0022-0000(91)90023-X