Department of
Applied
Mathematics

Multi-Level Steiner Tree

Stephen Kobourov

University of Arizona

Abstract

In the classical Steiner tree problem, one is given an undirected, connected graph G = (V, E) with non-negative edge costs and a set of terminals T. The objective is to find a minimum cost edge set that spans the terminals. The problem is NP-hard but can be approximated to within a small constant (the best known approximation algorithm has a ratio of ln(4), or about 1.39).

We study a natural generalization -- the multi-level Steiner tree (MLST) problem: given a nested sequence of terminals on k levels, T_1 subset ... subset T_k, compute nested edge sets E_1 subset ... subset E_k that span the corresponding terminal sets with minimum total cost. We first present two simple greedy approaches with approximation factor O(k). Based on these, we introduce a composite algorithm that does not depend on the number of levels. We also describe an integer linear program for the MLST problem which is used to empirically evaluate the performance of our algorithms.