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 [H.-C. Wirth, J. Steffan, Reload cost problems: Minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73–85]. In this model an undirected edge-coloured graph GG is given, together with a nonnegative symmetrical integer matrix RR specifying the costs of changing from a colour to another one. The reload cost of a path in GG 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 GG having a minimum diameter with respect to reload costs, when restricted to graphs with maximum degree 4, cannot be approximated within any constant α<2α<2 if the reload costs are unrestricted, and cannot be approximated within any constant β<5/3β<5/3 if the reload costs satisfy the triangle inequality. This solves a problem left open by Wirth and Steffan [H.-C. Wirth, J. Steffan, Reload cost problems: minimum diameter spanning tree, Discrete Appl. Math. 113 (2001) 73–85].