Class Steiner trees and VLSI-design

We consider a generalized version of the Steiner problem in graphs, motivat ed by the wire routing phase in physical VLSI design: given a connected, un directed distance graph with required classes of vertices and Steiner verti ces, find a shortest connected subgraph containing at least one vertex of e ach required class. We show that this problem is NP-hard, even if there are no Steiner vertices and the graph is a tree. Moreover, the same complexity result holds if the input class Steiner graph additionally is embedded in a unit grid, if each vertex has degree at most three, and each class consis ts of no more than three vertices. For similar restricted versions, we prov e MAX SNP-hardness and we show that there exists no polynomial-time approxi mation algorithm with a constant bound on the relative error, unless P = NP . We propose two efficient heuristics computing different approximate solut ions in time O(\E\ + \V\ log \V\) and in time O(c(\E\ + \V\ log \V\)), resp ectively, where E is the set of edges in the given graph, V is the set of v ertices, and c is the number of classes. We present some promising implemen tation results. (C) 1999 Elsevier Science B.V. All rights reserved.