The minimum latency problem is NP-hard for weighted trees

In the minimum latency problem (MLP) we are given n points v ₁,..., v _n and a distance d(v _i, v _j) between any pair of points. We have to find a tour, starting at v ₁ and visiting all points, for which the sum of arrival times is minimal. The arrival time at a point vi is the traveled distance from v ₁ to v _i in the tour. The minimum latency problem is MAX-SNP-hard for general metric spaces, but the complexity for the problem where the metric is given by an edge-weighted tree has been a long-standing open problem. We show that the minimum latency problem is NP-hard for trees even with weights in {0, 1}.