The k-hop connected dominating set problem: approximation and hardness

Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph ( $${\textsc {Min}}k{\hbox {-}\textsc {CDS}}$$ M I N k - CDS ). We prove that $${\textsc {Min}}k{\hbox {-}\textsc {CDS}}$$ M I N k - CDS is $$\mathscr {NP}$$ NP -hard on planar bipartite graphs of maximum degree 4. We also prove that $${\textsc {Min}}k{\hbox {-}\textsc {CDS}}$$ M I N k - CDS is $$\mathscr {APX}$$ APX -complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for $${\textsc {Min}}k{\hbox {-}\textsc {CDS}}$$ M I N k - CDS on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for $${\textsc {Min}}k{\hbox {-}\textsc {CDS}}$$ M I N k - CDS . Finally, when $$k=1$$ k = 1 , we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators.