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

For a graph , a dominating set is a set such that every vertex has a neighbor in . The minimum outer-connected dominating set (Min-Outer-Connected-Dom-Set) problem for a graph is to find a dominating set of such that , the induced subgraph by on , is connected and the cardinality of 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 for any , unless NP DTIME(). For sufficiently large values of , we show that for graphs with maximum degree , the Min-Outer-Connected-Dom-Set problem cannot be approximated within a factor of for some constant , unless P NP. On the positive side, we present a -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.