Doctoral Thesis
DOI
https://doi.org/10.11606/T.45.2017.tde-27062017-101521
Document
Author
Full name
Rafael Santos Coelho
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2017
Supervisor
Committee
Wakabayashi, Yoshiko (President)
Campêlo Neto, Manoel Bezerra
Gruber, Aritanan Borges Garcia
Lee, Orlando
Rey, Mário Leston
Title in English
The k-hop connected dominating set problem: approximation algorithms and hardness results
Keywords in English
Approximation algorithms
Computational complexity
Inapproximability threshold
K-disruptive separator
K-hop connected dominating set
Polyhedra
Abstract in English
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.
Title in Portuguese
O problema do conjunto dominante conexo com k-saltos: aproximação e complexidade
Keywords in Portuguese
Algoritmos de aproximação
Complexidade computacional
Conjunto dominante conexo de k-saltos
Limiar de inaproximabilidade
Poliedro
Separador k-disruptivo minimal
Abstract in Portuguese
Seja G um grafo conexo e k um inteiro positivo. Um subconjunto D de vértices de G é um conjunto dominante conexo de k-saltos se o subgrafo de G induzido por D é conexo e se, para todo vértice v em G, existe um vértice u em D a uma distância não maior do que k de v. Estudamos neste trabalho o problema de se encontrar um conjunto dominante conexo de k-saltos com cardinalidade mÃnima (Mink-CDS). Provamos que Mink-CDS é NP-difÃcil em grafos planares bipartidos com grau máximo 4. Mostramos que Mink-CDS é APX-completo em grafos bipartidos com grau máximo 4. Apresentamos limiares de inaproximabilidade para Mink-CDS para grafos bipartidos e (1, 2)-split, sendo que um desses é expresso em função de um parâmetro independente da ordem do grafo. Também discutimos a complexidade computacional do problema de se computar tal parâmetro. No lado positivo, propomos um algoritmo de aproximação para Mink-CDS cuja razão de aproximação é melhor do que a que se conhecia para esse problema. Finalmente, quando k = 1, apresentamos dois novos algoritmos de aproximação para a versão do problema com pesos nos vértices, sendo que um deles restrito a classes de grafos com um número polinomial de separadores minimais. Além disso, discutimos uma formulação de programação linear inteira para essa versão do problema e provamos resultados poliédricos a respeito de algumas das desigualdades que constituem o politopo associado à formulação.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2017-08-29