Technical Report No. 32, July 1991 - Abstract

Edmund Ihler:
The Complexity of Approximating the Class Steiner Tree Problem

Given a connected, undirected distance graph with required classes of nodes and optional Steiner nodes, find a shortest tree containing at least one node of each required class. This problem called Class Steiner Tree ist NP-hard and therefore we are dependent on approximation.

In this paper, we investigate various restrictions of the problem comparing their complexities with respect to approximability. A main result is that for an input of trees without Steiner nodes and unit edges only, Class Steiner Tree ist as hard to approximate as minimum set cover, for which no constant approximation is known, too. Further we prove that if this restricted version has an approximation scheme, all members of the optimization problem class MAX SNP do.