Given an undirected graph G = (V, E) and a cost vector c ∈ R(E), the weighted girth problem is to find a circuit in G having minimum total cost. This problem is in general NP-hard. A promising approach to the solution of hard combinatorial optimization problems is given by the so-called cutting plane methods. These involve linear programming techniques based on a partial description of the convex hull of the incidence vectors of possible solutions. We consider the weighted girth problems in the case where G is the complete graph Kn and study the facial structure of the circuit polytope P − C(n) and some related polyhedra. In the appendix we give complete characterizations of P − C(n) for n up to 6. We were motivated to study the weighted girth problem by the fact that this problem and variations of it appear as a subproblem, namely the pricing problem, in a column generation approach to the vehicle routing problem.
