On the cycle polytope of a directed graph

We give a partial description of the cycle polytope of a directed graph G, that is, the convex hull of the incidence vectors of simple directed cycles of G. First, we show how to obtain facets of the cycle polytope from facet s of the asymmetric traveling salesman polytope. This involves lifting and facet projection. We discuss several lifting procedures. Next, we obtain fa cets that have a different source. In particular, we give a complete charac terization of the facets that cut off the origin. No such characterization is known for the cycle polytope of an undirected graph. Finally, we introdu ce a useful equivalence class among the inequalities defining the cycle pol ytope. (C) 2000 John Wiley & Sons, Inc.