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 the authors 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=Θ, and it becomes the ATS polytope when F is the entire node set. The authors 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 inequalitiy for the ATS polytope to also be facet defining for the FDA polytope. The authors then introduce the class of FD inequalities and show that they define facets of both the ATS polytope and the FDA polytope. Finally, they 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.