Hardness Results of Connected Power Domination for Bipartite Graphs and Chordal Graphs

Abstract

A set $D \subseteq V$ of a graph $G=(V,E)$ is called a connected power dominating set of G if G[D], the subgraph induced by D, is connected and every vertex in the graph can be observed from D, following the two observation rules for power system monitoring: Rule 1: if $v \in D$, then v can observe itself and all its neighbors, and Rule 2: for an already observed vertex whose all neighbors except one are observed, then the only unobserved neighbor becomes observed as well. Minimum Connected Power Domination Problem is to find a connected power dominating set of minimum cardinality of a given graph G and Decide Connected Power Domination Problem is the decision version of Minimum Connected Power Domination Problem. Decide Connected Power Domination Problem is known to be NP-complete for general graphs. In this paper, we strengthen this result by proving that Decide Connected Power Domination Problem remains NP-complete for perfect elimination bipartite graph, a proper subclass of bipartite graphs, and split graphs, a proper subclass of chordal graphs. On the positive side, we show that Minimum Connected Power Domination Problem is polynomial-time solvable for chain graphs, a proper subclass of perfect elimination bipartite graph, and for threshold graphs, a proper subclass of split graphs. Further, we show that Minimum Connected Power Domination Problem cannot be approximated within $(1-\epsilon )\ln \vert V \vert$ for any $\epsilon >0$ unless $\textsf {P}=\textsf {NP}$, for bipartite graphs as well as for chordal graphs.