Requiring Connectivity in the Set Covering Problem

Given a bipartite graph with bipartition V and W, a cover is a subset C $${\subseteq}$$ V such that each node of W is adjacent to at least one node in C. The set covering problem seeks a minimum cardinality cover. Set covering has many practical applications. In the context of reserve selection for conservation of species, V is a set of candidate sites from a reserve network, W is the set of species to be protected, and the edges describe which species are represented in each site. Some covers however may assume spatial configurations which are not adequate for conservational purposes. Indeed, for sustainability reasons the fragmentation of existing natural habitats should be avoided, since this is recognized as being disruptive to the species adapted to the habitats. Thus, connectivity appears to be an important issue for protection of biological diversity. We therefore consider along with the bipartite graph, a graph G with node set V, describing the adjacencies of the elements of V, and we look for those covers C $${\subseteq}$$ V for which the subgraph of G induced by C is connected. We call such covers connected covers. In this paper we introduce and study some valid inequalities for the convex hull of the set of incidence vectors of connected covers.