On the p-median polytope and the directed odd cycle inequalities: Triangle-free oriented graphs

Abstract

We study the effect of the odd directed cycle inequalities in the description of the polytope associated with the p-median problem. We treat oriented graphs, i.e., if (u,v) is in the arc-set, then (v,u) is not in the arc-set. We characterize the oriented graphs for which the obvious linear relaxation together with the directed odd cycle inequalities describe the p-median polytope. This study has two parts: in this paper we treat triangle-free graphs, then in a second paper we use induction on the number of triangles to treat general oriented graphs.