- INSTANCE:
Complete graph
,
weight
for each
,
requirement
for each pair of
vertices from
*V*. - SOLUTION:
A spanning tree for
*G*. - MEASURE:
The weighted sum over all pairs of vertices of the cost of
the path between the pair in
*T*, i.e., , where*W(u,v)*denotes the sum of the weights of the edges on the path joining*u*and*v*in*T*.

*Good News:*Approximable within if the weight function satisfies the triangle inequality [397].*Comment:*MINIMUM ROUTING COST SPANNING TREE, the variation in which for all*u,v*, admits a PTAS [469].*Garey and Johnson:*ND7