The Rainbow Cycle Cover Problem

We model and solve the Rainbow Cycle Cover Problem (RCCP). Given a connected and undirected graph G = ( V , E , L ) and a coloring function 𝓁 that assigns a color to each edge of G from the finite color set L , a cycle whose edges have all different colors is called a rainbow cycle. The RCCP consists of finding the minimum number of disjoint rainbow cycles covering G . The RCCP on general graphs is known to be NP‐complete. We model the RCCP as an integer linear program, we derive valid inequalities and we solve it by branch‐and‐cut. Computational results are reported on randomly generated instances.