On the p-Median Polytope and the Directed Odd Cycle Inequalities I: Triangle-Free Oriented Graphs

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