FACETS OF 2 STEINER ARBORESCENCE POLYHEDRA

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. In the present paper we study the facial structure of two polyhedra associated with the problem. Several classes of valid inequalities are considered, and a new class with arbitrarily large coefficients is introduced. All these inequalities are shown to define distinct facets of both the Steiner polyhedra considered. This is achieved by exploiting two lifting theorems which also allow generalization of the new inequalities. Composition theorems are finally given and used to derive large families of new facet-inducing inequalities with exponentially large coefficients.