On the Complexity of Constructing Minimum Reload Cost Path-Trees
The reload cost concept refers to the cost that occurs at a vertex along a path on an edge-colored graph when it traverses an internal vertex between two edges of different colors. The reload cost depends only on the colors of the traversed edges. Previous work on reload costs focuses on the problem of finding a spanning tree that minimizes the total reload cost from a source vertex to all other vertices in a directed graph and proves that this problem is not approximable within any polynomial time computable function of the input size. In this paper, the authors study the complexity and approximability properties of numerous special cases of this problem.