Special Issue for FAW 2014

For a graph (G=(V,E)), a dominating set is a set (Dsubseteq V) such that every vertex (vin Vsetminus 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[Vsetminus D]), the induced subgraph by (G) on (Vsetminus 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.