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

Abstract

We introduce a new covering problem, called Component Cover by Vertices (CCV). In this problem, we are given a graph G and a partition A,B ofV(G), and our goal is to find the smallest subset B? ofB such that, for every connected component C ofG[A], there is a vertex v ∈ C with some neighbor in B?. We study the complexity of this problem and give positive and negative results. We show that the CCV problem is NP-Complete in several classes of graphs. We also show that the problem is hard to approximate and parame- terize. On the other hand, we present polynomial algorithms for other classes of graphs. Finnaly, we show FPT parameterizations and approximation algo- rithms for certain classes ofgraphs. Resumo.

Keywords: Graphs, Component Cover by Vertices

References

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.