This work draws attention to combinatorial network abstraction problems which are specified by a class
of pattern graphs and a real-valued similarity measure
based on certain graph properties. For fixed
, the optimization task on any graph
is to find a subgraph
′ which belongs to
. 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
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.