Seleção de Representantes para Cobertura de Componentes Conexas em Grafos

• Anderson Lemos UFMG
• Vinicius F. dos Santos UFMG
• Olga Goussevskaia UFMG

DOI: https://doi.org/10.5753/ctd.2019.6339

Resumo

Introduzimos um novo problema de cobertura chamado Cobertura de Componentes por Vértices (CCV). Neste problema são dados um grafo G e uma partição A e B de V(G), e nosso objetivo ´e encontrar o menor subconjunto B de B tal que, para cada componente conexa C de G[A], há um vértice v ∈ C com algum vizinho em B?. Estudamos a complexidade deste problema e damos resultados positivos e negativos. Mostramos que o problema CCV e NP- Completo para várias classes de grafos. Mostramos tamb´em que o problema é difícil de aproximar e de parametrizar. Por outro lado, apresentamos algoritmos polinomiais para outras classes de grafos. Por fim, mostramos parametrizações FPT e algoritmos aproximativos para determinadas classes de grafos.

Palavras-chave: Grafos, Cobertura de Componentes por Vertices

Referências

Alber, J., Bodlaender, H. L., Fernau, H., and Niedermeier, R. (2000). Fixed parameter algorithms for planar dominating set and related problems. In Scandinavian Workshop on Algorithm Theory, pages 97–110. Springer.

Bar-Yehuda, R. and Even, S. (1985). A local-ratio theorem for approximating the weigh- ted vertex cover problem. North-Holland Mathematics Studies, 109:27–45.

Bondy, J. A., Murty, U. S. R., et al. (1976). Graph theory with applications, volume 290. Citeseer.

Brandstadt, A., Spinrad, J. P., et al. (1999). Graph classes: a survey, volume 3. Siam.

Clark, B. N., Colbourn, C. J., and Johnson, D. S. (1990). Unit disk graphs. Discrete mathematics, 86(1-3):165–177.

Duh, R.-c. and F¨urer, M. (1997). Approximation of k-set cover by semi-local optimiza- tion. In Proceedings ofthe twenty-ninth annual ACM symposium on Theory ofcompu- ting, pages 256–264. ACM.

Feige, U. (1998). A threshold of ln n for approximating set cover. Journal of the ACM (JACM), 45(4):634–652.

Ferreira Neto, M., Goussevskaia, O., and dos Santos, V. F. (2017). Connectivity with backbone structures in obstructed wireless networks. Computer Networks, 127:266 – 281.

Garnero, V., Sau, I., and Thilikos, D. M. (2017). A linear kernel for planar red–blue dominating set. Discrete Applied Mathematics, 217:536–547.

Levin, A. (2008). Approximating the unweighted k-set cover problem: greedy meets local search. SIAM Journal on Discrete Mathematics, 23(1):251–264.

Vazirani, V. V. (2013). Approximation algorithms. Springer Science & Business Media. Wu, W., Du, H., Jia, X., Li, Y., and Huang, S. C.-H. (2006). Minimum connected domi- nating sets and maximal independent sets in unit disk graphs. Theoretical Computer Science, 352(1-3):1–7.