Spanning Trees in Hypergraphs with Applications to Steiner Trees

This dissertation examines the geometric Steiner tree problem: given a set of terminals in the plane, find a minimum-length interconnection of those terminals according to some geometric distance metric. In the process, however, it addresses a much more general and widely applicable problem, that of finding a minimum-weight spanning tree in a hypergraph.

geometric Steiner tree problem is known to be NP-complete for the rectilinear metric, and NP-hard for the Euclidean metric. The fastest exact algorithms (in practice) for these problems use two phases: First a small but sufficient set of full Steiner trees (FSTs) is generated and then a Steiner minimal tree is constructed from this set. These phases are called FST generation and FST concatenation, respectively, and an overview of each phase is presented. FST concatenation is almost always the most expensive phase, and has traditionally been accomplished via simple backtrack search or dynamic programming.

The spanning tree in hypergraph problem is defined, and is proven to be strongly NP-complete. The minimum-weight spanning tree (MST) in hypergraph problem is then motivated by showing that FST concatenation reduces to MST in hypergraph in a simple way. The MST in hypergraph problem is then formulated as an integer program using subtour elimination constraints. The spanning tree in hypergraph polytope, STHGP(n), is introduced and a number of its properties are proven. In particular, every constraint used in the integer program is shown to define a facet of STHGP(n). An alternate integer programming formulation based on cutset constraints is presented, but is shown to have an LP relaxation that is weaker than that of the subtour formulation. A simple formula for the number of extreme points in STHGP(n) is shown, thereby generalizing the classical tree enumeration problem of Cayley to hypergraphs.

A branch-and-cut algorithm for the MST in hypergraph problem is presented. This algorithm is applied to the FST concatenation problem. Experimental results are presented for a large set of problem instances of various sizes up to 1000 terminals. Optimal rectilinear and Euclidean Steiner trees are obtained for every instance. A single 2000 terminal Euclidean instance is also solved to optimality. These results show that the new algorithm is by far the fastest in existence, since the best previously published Steiner tree results are 70 terminals for rectilinear and 150 terminals for Euclidean, respectively.

A number of directions for future work are outlined, and in conclusion it is noted that this two-phase approach works for any distance metric in any nite dimension -- even the Steiner problem in graphs -- provided a suitable FST generation algorithm is available.