Computing a minimum outer-connected dominating set for the class of chordal graphs

• We study the algorithmic complexity of minimum outer-connected dominating set problem for the class of chordal graphs.
• We present a linear time algorithm for finding a minimum outer-connected dominating set in proper interval graphs.
• We prove that the minimum outer-connected dominating set problem is NP-complete for doubly chordal graphs and undirected path graphs.

For a graph G=(V,E)G=(V,E), a dominating set   is a set D⊆VD⊆V such that every vertex v∈V∖Dv∈V∖D has a neighbor in D  . Given a graph G=(V,E)G=(V,E) and a positive integer k, the minimum outer-connected dominating set problem for G is to decide whether G has a dominating set D of cardinality at most k   such that G[V∖D]G[V∖D], the induced subgraph by G   on V∖DV∖D, is connected. In this paper, we consider the complexity of the minimum outer-connected dominating set problem for the class of chordal graphs. In particular, we show that the minimum outer-connected dominating set problem is NP-complete for doubly chordal graphs and undirected path graphs, two well studied subclasses of chordal graphs. We also give a linear time algorithm for computing a minimum outer-connected dominating set in proper interval graphs. Notice that proper interval graphs form a subclass of undirected path graphs as well as doubly chordal graphs.