Minimum reload cost cycle cover in complete graphs

Abstract

The reload cost refers to the cost that occurs along a path on an edge-colored graph when it traverses an internal vertex between two edges of different colors. Galbiati et al. introduced the Minimum Reload Cost Cycle Cover problem, which is to find a set of vertex-disjoint cycles spanning all vertices with minimum reload cost. They proved that this problem is strongly NP-hard and not approximable within 1/epsilon for any epsilon > 0 even when the number of colors is 2, the reload costs are symmetric and satisfy the triangle inequality. In this paper, we prove that the minimum reload cost is zero on complete graphs with n vertices and an equitable 2-edge-coloring except possibly n = 4 or with a nearly equitable 2-edge-coloring except possibly for n <= 13. Furthermore, we provide a polynomial-time algorithm that constructs a monochromatic cycle cover in complete graphs K-n with an equitable 2-edge-coloring except possibly for n = 4. This algorithm also finds a monochromatic cycle cover in complete graphs with a nearly equitable 2-edge-coloring except for some special cases.