On the Cycle Polytope of a Directed Graph and Its Relaxations

This paper continues the investigation of the cycle polytope of a directed graph begun by Balas and Oosten [2]. Given a digraph G = (N,A) and the collection C of its simple directed cycles, the cycle polytope defined on G is P C ≔ conv {X C :C∈C}, where χ C is the incidence vector of C. According to the integer programming formulation given in [2], P C is the convex hull of points x∈ℝ satisfying (1) $$ x(\delta ^ + (i)) - x(\delta ^ - (i)) = 0{\text{ }}for{\text{ all }}i \in N $$ , (2) $$ x(\delta ^ + (i)) \leqslant 1{\text{ }}for{\text{ all }}i \in N $$ , (3) $$ \begin{array}{*{20}c} { - x(S,N\backslash S) + x(\delta ^ + (i)) + x(\delta ^ + (j)) \leqslant 1{\text{ }}for{\text{ all }}S \subseteq N,2 \leqslant |S| \leqslant n - 2,} \\ {i \in S,j \in N\backslash S} \\ \end{array} $$ , (4) $$ \sum\limits_{i = 1}^{n - 1} {\sum\limits_{j = i + 1}^n {x_{\pi (i)\pi (j)} } \geqslant 1{\text{ for all permutations }}\pi {\text{ of }}N} $$ , (5) $$ x_{ij} \in \{ 0,1\} {\text{ }}for all (i,j) \in A $$