Special Issue for FAW 2014

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 \(GV\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.