THE FIXED-OUTDEGREE 1-ARBORESCENCE POLYTOPE

A 1-arborescence is a spanning arborescence rooted at node 1, plus one arc incident into node 1. The 1-arborescence polytope, the convex hull of incidence vectors of 1-arborescences, is a well-known relaxation of the Asymmetric Traveling Salesman (ATS) polytope. In this paper we study the Fixed Outdegree 1-Arborescence (FDA) polytope, defined as the convex hull of incidence vectors of 1-arborescences having outdegree 1 at a prescribed subset F of nodes. The FDA polytope becomes the 1-arborescence polytope when F = empty set, and it becomes the ATS polytope when F is the entire node set. We derive several classes of valid inequalities for the FDA polytope and show that they are facet defining. This is done by using a theorem that establishes sufficient conditions for a facet defining inequality for the ATS polytope to also be facet defining for the FDA polytope. We then introduce the class of FD inequalities and show that they define facets of both the ATS polytope and the FDA polytope. Finally, we define a canonical form that facilitates rigorous comparisons between inequalities, and use it to show that the new facets are distinct from each other and from other known facets.