The Facets of the Subtours Elimination Polytope

Abstract

Let $G=(V,E)$ be an undirected graph. The subtours elimination polytope $P(G)$ is the set of $x\in {\mathbb{R}}^E$ such that: $0\le x(e)\le 1$ for any edge $e\in E$, $x(\delta (v))=2$ for any vertex $v\in V$, and $x(\delta (U))\ge 2$ for any nonempty and proper subset $U$ of $V$. $P(G)$ is a relaxation of the Traveling Salesman Polytope, i.e., the convex hull of the Hamiton circuits of $G$. Maurras \cite{Maurras 1975} and Grötschel and Padberg \cite{Grotschel and Padberg 1979b} characterize the facets of $P(G)$ when $G$ is a complete graph. In this paper we generalize their result by giving a minimal description of $P(G)$ in the general case and by presenting a short proof of it.