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

Abstract

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.