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

• Ano de defesa: 2017
• Autor(a) principal: Coelho, Rafael Santos
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Algoritmos de aproximação; Approximation algorithms; Complexidade computacional; Computational complexity; Conjunto dominante conexo de k-saltos; Inapproximability threshold; K-disruptive separator; K-hop connected dominating set; Limiar de inaproximabilidade; Poliedro; Polyhedra; Separador k-disruptivo minimal
• Link de acesso: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/

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 (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar- tite 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 complex- ity of computing this graph parameter. On the positive side, we show an approximation algorithm for Mink-CDS. When k = 1, we present two new approximation algorithms for the weighted version of the problem, one of them restricted to graphs with a poly- nomially bounded number of minimal separators. Finally, also for the weighted variant of the problem where k = 1, we discuss an integer linear programming formulation and conduct a polyhedral study of its associated polytope.