Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs

Abstract

A set D ⊆ V of a graph G = (V,E) is called an outer-connected dominating set of G if for all v ∈ V, |N_G[v]∩D| ≥ 1, and the induced subgraph of G on V\D is connected. The MINIMUM OUTER-CONNECTED DOMINATION problem is to find an outer-connected dominating set of minimum cardinality of the input graph G. Given a positive integer k and a graph G=(V,E), the OUTER-CONNECTED DOMINATION DECISION problem is to decide whether G has an outer-connected dominating set of cardinality at most k. The OUTER-CONNECTED DOMINATION DECISION problem is known to be NP-complete for bipartite graphs. In this paper, we strengthen this NP-completeness result by showing that the OUTER-CONNECTED DOMINATION DECISION problem remains NP-complete for perfect elimination bipartite graphs. On the positive side, we propose a linear-time algorithm for computing a minimum outer-connected dominating set of a chain graph, a subclass of bipartite graphs. We show that the OUTER-CONNECTED DOMINATION DECISION problem can be solved in linear-time for graphs of bounded tree-width. We propose a ∆(G)-approximation algorithm for the MINIMUM OUTER-CONNECTED DOMINATION problem, where ∆(G) is the maximum degree of G. On the negative side, we prove that the MINIMUM OUTER-CONNECTED DOMINATION problem cannot be approximated within a factor of (1−ε)ln|V| for any ε > 0, unless NP ⊆ DTIME(|V|^O(loglog|V|)). We also show that the MINIMUM OUTER-CONNECTED DOMINATION problem is APX-complete for graphs with bounded degree 4 and for bipartite graphs with bounded degree 7.