We consider the collection of all spanning trees of a graph with distance between them based on the size of the symmetric difference of their edge sets. A central spanning tree of a graph is one for which the maximal distance to all other spanning trees is minimal. We prove that the problem of constructing a central tree is algorithmically difficult and leads to an NP-complete problem.

[PS] [PS.GZ]