  We consider a new Steiner tree problem, called vertex-cover-weighted Steiner
tree problem. This problem defines the weight of a Steiner tree as the minimum
weight of vertex covers in the tree, and seeks a minimum-weight Steiner tree in
a given vertex-weighted undirected graph. Since it is included by the Steiner
tree activation problem, the problem admits an O(log n)-approximation algorithm
in general graphs with n vertices. This approximation factor is tight up to a
constant because it is NP-hard to achieve an o(log n)-approximation for the
vertex-cover-weighted Steiner tree problem on general graphs even if the given
vertex weights are uniform and a spanning tree is required instead of a Steiner
tree. In this paper, we present constant-factor approximation algorithms for
the problem with unit disk graphs and with graphs excluding a fixed minor. For
the latter graph class, our algorithm can be also applied for the Steiner tree
activation problem.

Data Structures and Algorithms