ON THE INTEGRAL DICYCLE PACKINGS AND COVERS AND THE LINEAR ORDERING POLYTOPE

The linear ordering polytope P-LO(n), is defined as the convex hull of all the incidence vectors of the acyclic tournaments on n nodes. It i s known that for every facet of P-LO(n), there corresponds a digraph i nducing it. Let D be a digraph that induces a facet-defining inequalit y for P-LO(n), that is nonequivalent to a trivial inequality or to a 3 -dicycle inequality. We show that for such a digraph the following hol ds: the value tau of a minimum integral dicycle cover is greater than the value tau of a minimum dicycle cover. We show that tau* can be fo und by minimizing a linear function over a polytope which is defined b y a polynomial number of constraints. Let nu denote the value of a max imum integral dicycle packing. We prove that if D is a certain digraph with a two-node cut satisfying tau = nu in each part, then tau = nu i n D as well. Dridi's description of P-LO(5) enables a simple derivatio n of the fact that tau = nu for any digraph on 5 nodes. Combining thes e results with the theorem of Lucchesi and Younger for planar digraphs as well as Wagner's decomposition, we obtain that tau = nu in K-3,K-3 -free digraphs. This last result was proved recently by Barahona et al . (1990) using polyhedral techniques while our proof is based mainly o n combinatorial tools.