On the complexity of the minimum outer-connected dominating set problem in graphs

详细信息    查看全文

• 作者：D. Pradhan
• 关键词：Dominating set ; Outer ; connected dominating set ; NP ; complete ; APX ; complete
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：31
• 期：1
• 页码：1-12
• 全文大小：505 KB
• 参考文献：Aho AV, Hopcroft JE, Ullman JD (2001) The design and analysis of computer algorithms. Addison-Wesley, Reading, MA
  Akhbari MH, Hasni R, Favaron O, Karami H, Sheikholeslami SM (2013) On the outer-connected domination in graphs. J Comb Optim 26:10–18MathSciNet CrossRef MATH
  Alimonti P, Kann V (1997) Hardness of approximating problems on cubic graphs. In: Proceedings of 3rd Italian conference on algorithms and complexity, Rome, Lecture Notes in Computer Science, vol 1203, pp 288–298
  Arora S, Lund C (1996) Hardness of approximation. In: Hochbaum D (ed) Approximation algorithms for NP-hard problems. PWS Publishing, Boston
  Chlebík M, Chlebíková J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Inf Comput 206:1264–1275CrossRef MATH
  Cyman J (2007) The outer-connected domination number of a graph. Australas J Comb 38:35–46MathSciNet MATH
  Cyman J (2010) Total outer-connected domination in trees. Discuss Math Graph Theory 30:377–383MathSciNet CrossRef MATH
  Cyman J, Raczek J (2009) Total outer-connected domination numbers of trees. Discrete Appl Math 157:3198–3202MathSciNet CrossRef MATH
  Favaron O, Karami H, Sheikholeslami SM (2012) On the total outer-connected domination in graphs. J Comb Optim. doi:10.​1007/​s10878-012-9531-6
  Feige U (1998) A threshold of \(\ln n\) for approximating set cover. JACM 45(4):634–652MathSciNet CrossRef MATH
  Haynes TW, Hedetniemi ST, Slater PJ (eds) (1998a) Domination in graphs. Marcel Dekker Inc, New York, advanced topics.
  Haynes TW, Hedetniemi ST, Slater PJ (1998b) Fundamentals of domination in graphs. Marcel Dekker Inc., New YorkMATH
  Jiang H, Shan E (2010) Outer-connected domination number in graphs. Util Math 81:265–274MathSciNet MATH
  Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations, proceedings of symposium IBM Thomas J. Watson Res. Center, Yorktown Heights, New York, pp 85–103
  Keil JM, Pradhan D (2013) Computing a minimum outer-connected dominating set for the class of chordal graphs. Inf Process Lett 113:552–561MathSciNet CrossRef MATH
  Papadimitriou CH, Yannakakis M (1991) Optimization, approximation and complexity classes. J Comput Syst Sci 43:425–440MathSciNet CrossRef MATH
  Trevisan L (2001) Non-approximability results for optimization problems on bounded degree instances. In: Proceedings of the 33rd ACM STOC, pp 453–461
  
• 作者单位：D. Pradhan (1)
  
  1. Indian Institute of Technology, Jodhpur, Rajasthan, India
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

For a graph \(G=(V,E)\), a dominating set is a set \(D\subseteq V\) such that every vertex \(v\in V\setminus D\) has a neighbor in \(D\). The minimum outer-connected dominating set (Min-Outer-Connected-Dom-Set) problem for a graph \(G\) is to find a dominating set \(D\) of \(G\) such that \(G[V\setminus D]\), the induced subgraph by \(G\) on \(V\setminus D\), is connected and the cardinality of \(D\) is minimized. In this paper, we consider the complexity of the Min-Outer-Connected-Dom-Set problem. In particular, we show that the decision version of the Min-Outer-Connected-Dom-Set problem is NP-complete for split graphs, a well known subclass of chordal graphs. We also consider the approximability of the Min-Outer-Connected-Dom-Set problem. We show that the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \((1-\varepsilon ) \ln |V|\) for any \(\varepsilon >0\), unless NP \(\subseteq \) DTIME(\(|V|^{\log \log |V|}\)). For sufficiently large values of \(\varDelta \), we show that for graphs with maximum degree \(\varDelta \), the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of \(\ln \varDelta -C \ln \ln \varDelta \) for some constant \(C\), unless P \(=\) NP. On the positive side, we present a \(\ln (\varDelta +1)+1\)-factor approximation algorithm for the Min-Outer-Connected-Dom-Set problem for general graphs. We show that the Min-Outer-Connected-Dom-Set problem is APX-complete for graphs of maximum degree 4.