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

For a graph $$G=(V,E)$$ G = ( V , E ) , a dominating set is a set $$D\subseteq V$$ D ⊆ V such that every vertex $$v\in V\setminus D$$ v ∈ V \ D has a neighbor in $$D$$ D . The minimum outer-connected dominating set (Min-Outer-Connected-Dom-Set) problem for a graph $$G$$ G is to find a dominating set $$D$$ D of $$G$$ G such that $$G[V\setminus D]$$ G [ V \ D ] , the induced subgraph by $$G$$ G on $$V\setminus D$$ V \ D , is connected and the cardinality of $$D$$ 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|$$ ( 1 - ε ) ln | V | for any $$\varepsilon >0$$ ε > 0 , unless NP $$\subseteq $$ ⊆ DTIME( $$|V|^{\log \log |V|}$$ | 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 $$ ln Δ - C ln ln Δ for some constant $$C$$ C , unless P $$=$$ = NP. On the positive side, we present a $$\ln (\varDelta +1)+1$$ 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.