The Complexity of a Minimum Reload Cost Diameter Problem

We consider the minimum diameter spanning tree problem under the reload cost model which has been introduced by Wirth and Steffan in [Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001), 73–85]. In this model an undirected edge-coloured graph G is given, together with a nonnegative symmetrical integer matrix R specifying the costs of changing from a colour to another one. The reload cost of a path in G arises at its internal nodes, when passing from the colour of one incident edge to the colour of the other. We prove that, unless P = NP, the problem of finding a spanning tree of G having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant less than 2 if the reload costs are unrestricted, and cannot be approximated within any constant less than 5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan in loc. cit.