Given a bipartite graph G=(V,U,E), a cover of G is a subset D⊆V with the property that each node u∈U is adjacent to at least one node v∈D. If a positive weight cn is associated with each node v∈V, the covering problem (CP) is to find a cover of G having minimum total weight. In this paper we study the properties of the polytope Q(G)ℝℝ’∈V’∈, the convex hull of the incidence vectors of all the covers in G. After discussing some general properties of Q(G) we introduce a large class of bipartite graphs with special structure and describe several types of rank facets of the associated polytopes. Furthermore we present two lifting procedures to derive valid inequalities and facets of the polytope Q(G) from the facets of any polytope Q(G') associated with a subgraph G' of G. An example of the application of the theory to a class of hard instances of the covering problem is also presented.
