Some Formulations for the Group Steiner Tree Problem

The group Steiner tree problem consists of, given a graph G, a collection R of subsets of V ( G ) and a cost c ( e ) for each edge of G, find a minimum-cost subgraph that connects at least one vertex from each R ∈ R . It is a generalization of the well-known Steiner tree problem that arises naturally in the design of VLSI chips. In this paper, we study a polyhedron associated with this problem and some extended formulations. We give facet defining inequalities and explore the relationship between the group Steiner tree problem and other combinatorial optimization problems.