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

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.