Seleção de representantes para cobertura de componentes conexas em grafos

A partir da generalização de problemas de conectividade em redes de comunicação ad hoc, amplamente estudados na literatura, introduzimos um novo problema de cobertura, chamado Component Cover by Vertices (CCV). Neste problema, são dados um grafo G e uma partição A, B de V(G), e nosso objetivo é encontrar o menor subconjunto B' de B tal que, para cada componente conexa C de G [A], há um vértice v C tal que v tem um vizinho em B '. Estudamos a complexidade deste problema e damos resultados positivos e negativos. Em particular, mostramos que o problema CCV é NP-Completo para várias classes de grafos, como cordais, bipartidos com grau de vértice no máximo três, UDGs planares e grades. Além disso, mostramos que o problema também é difícil de aproximar. Também discutimos uma conexão entre CCV e o problema Reb-Blue Dominating Set, deduzindo que CCV é W[2]-Completo em grafos gerais. Por outro lado, apresentamos algoritmos polinomiais para as classes de grafos de blocos, co-grafos, cactos e outerplanares. Mostramos que o problema é FPT se parametrizado por largura arbórea ou por tamanho da solução e grau máximo. Por fim, mostramos dois algoritmos aproximativos para grafos gerais e um algoritmo aproximativo de fator constante para a classe de UDGs. Based on the generalization of connectivity problems in ad hoc communication networks, widely studied in the literature, we introduce a new covering problem, called Componet Cover by Vertices (CCV). In this problem, we are given a graph G and a partition A, B of V(G), and our goal is to find the smallest subset B' of B such that, for every connected component C of G[A], there is a vertex v C such that v has a neighbor in B'. We study the complexity of this problem and give positive and negative results. In particular, we show that the CCV problem is NP-Complete in several classes of graphs, such as chordal, bipartite with vertex degree at most three, planar UDGs and grids. Moreover, we show that the problem is also hard to approximate. We also discuss a connection between CCV and the so called Reb Blue Dominating Set problem, deducing that CCV W[2]-Complete in general graphs. On the other hand, we present polynomial algorithms for the classes of graphs of blocks, co-graphs, cactus and outerplanares. We show that the problem is FPT if parameterized by treewidth or by solution size and maximum degree. Finally, we show two approximation algorithms for general graphs and a constant-factor approximation algorithm for the class of UDGs.