On the complexity of finding a minimum cycle cover of a graph. - Thomassen, Carsten
We prove that the problem of finding a cycle cover of smallest total length is NP-hard. This confirms a conjecture of Itai, Lipton, Papadimitriou and Rodeh from 1981.
Keywords: Complexity; Minimum cycle cover