The minimum vertex ranking spanning tree problem (MVRST) is to find a spanning tree of G whose vertex ranking is minimum. In this paper, we show that MVRST is NP-hard. To prove this, we polynomially reduce the 3-dimensional matching problem to MVRST. Moreover, we present a ([D-s/2] + 1)/([log(2)(D-s + 1)] + 1)-approximation algorithm for MVRST where D-s is the minimum diameter of spanning trees of G. (c) 2006 Elsevier B.V. All rights reserved.