Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Eighth International Workshop on Algorithms and Computation, WALCOM 2014
DOI: 10.7155/jgaa.00334
Algorithm and Hardness Results for Outerconnected Dominating Set in Graphs
B. S. Panda and
Arti Pandey
Vol. 18, no. 4, pp. 493513, 2014. Regular paper.
Abstract A set D ⊆ V of a graph G = (V,E) is called an outerconnected 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 OUTERCONNECTED DOMINATION problem is to find an outerconnected dominating set of minimum cardinality of the input graph G. Given a positive integer k and a graph G=(V,E), the OUTERCONNECTED DOMINATION DECISION problem is to decide whether G has an outerconnected dominating set of cardinality at most k. The OUTERCONNECTED DOMINATION DECISION problem is known to be NPcomplete for bipartite graphs. In this paper, we strengthen this NPcompleteness result by showing that the OUTERCONNECTED DOMINATION DECISION problem remains NPcomplete for perfect elimination bipartite graphs. On the positive side, we propose a lineartime algorithm for computing a minimum outerconnected dominating set of a chain graph, a subclass of bipartite graphs. We show that the OUTERCONNECTED DOMINATION DECISION problem can be solved in lineartime for graphs of bounded treewidth. We propose a ∆(G)approximation algorithm for the MINIMUM OUTERCONNECTED DOMINATION problem, where ∆(G) is the maximum degree of G. On the negative side, we prove that the MINIMUM OUTERCONNECTED DOMINATION problem cannot be approximated within a factor of (1−ε)lnV for any ε > 0, unless NP ⊆ DTIME(V^{O(loglogV)}). We also show that the MINIMUM OUTERCONNECTED DOMINATION problem is APXcomplete 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.
