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

Rafael S. Coelho (), Phablo F. S. Moura () and Yoshiko Wakabayashi ()
Additional contact information
Rafael S. Coelho: Universidade de São Paulo
Phablo F. S. Moura: Universidade de São Paulo
Yoshiko Wakabayashi: Universidade de São Paulo

Journal of Combinatorial Optimization, 2017, vol. 34, issue 4, No 5, 1060-1083

Abstract: Abstract 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.

Keywords: Approximation algorithms; Hardness; k-Hop connected dominating set; k-Disruptive separator (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0128-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:34:y:2017:i:4:d:10.1007_s10878-017-0128-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0128-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().