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) 7385]. In this model an undirected edge-coloured graph G G is given, together with a nonnegative symmetrical integer matrix R R specifying the costs of changing from a colour to another one. The reload cost of a path in G 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 G 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) 7385].
minimum diameter spanning tree reload cost model combinatorial optimization approximation algorithm