This work draws attention to combinatorial network abstraction problems which are specified by a class  P\mathcal{P} of pattern graphs and a real-valued similarity measure  r\varrho based on certain graph properties. For fixed  P\mathcal{P} and  r\varrho, the optimization task on any graph G is to find a subgraph G′ which belongs to  P\mathcal{P} and minimizes r(G,G^¢)\varrho(G,G^{\prime}). We consider this problem for the natural case of trees and distance-based similarity measures. In particular, we systematically study spanning trees of graphs that minimize distances, approximate distances, and approximate closeness-centrality with respect to some standard vector and matrix norms. The complexity analysis shows that all considered variants of the problem are NP-complete, except for the case of distance-minimization with respect to the L _∞ norm. We further show that unless P = NP, there exist no polynomial-time constant-factor approximation algorithms for the distance-approximation problems if a subset of edges can be forced into the spanning tree.