On the facial structure of Steiner Arborescence polytopes

The Steiner Arborescence (or Steiner Directed Tree) Problem concerns the connection of a set of target vertices of a digraph to a given root vertex. This problem is known to be NP-hard. This paper studies the facial structure of two polytopes associated with the problem. Several classes of valid inequalities are considered, and new inequalities having Chvatal-rank 1 are derived from them. All the inequalities are shown to define facets for both the Steiner polytopes considered. In addition, the paper proves that all the facets defined by the new inequalities which were introduced, are distinct.