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

For a graph G=(V,E), a dominating set is a set D⊆V such that every vertex v∈V\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\D], the induced subgraph by G on V\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-ε)ln|V| for any ε>0, unless NP ⊆ DTIME(|V|loglog|V|). 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 lnΔ-ClnlnΔ for some constant C, unless P = NP. On the positive side, we present a ln(Δ+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.