Algorithm and Hardness Results for Outer-connected Dominating Set in Graphs
B. S. Panda and Arti Pandey
Vol. 18, no. 4, pp. 493-513, 2014. Regular paper.
Abstract A set DV of a graph G = (V,E) is called an outer-connected dominating set of G if for all vV, |NG[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.
Submitted: March 2014.
Reviewed: June 2014.
Revised: July 2014.
Accepted: July 2014.
Final: December 2014.
Published: December 2014.
article (PDF)