# Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph

I've posted a question on Stack Overflow regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.

One of the respondents cited Professor David Speyer's Math Overflow post in Math Overflow saying it's a polytime problem, while I argued it is not as I believe the solution of my problem can be used to solve a smaller travelling salesman problem. Unfortunately, that debate kind of ended here because the respondent stopped replying (he probably is busy and have forgotten about it or thought I am inexorably ignorant). Anyhow, I can't really rest until I know for certain it's an NP-hard problem or not. Can you guys help out?

Added by Brendan: The problem is, given an undirected graph with edge weights, find a set of vertex-disjoint cycles covering all the vertices and with maximum total weight.

-

This problem is called "maximum cycle cover" and if you search with that phrase you'll find your answer. For example this paper says there is an $O(n^3)$ algorithm, but it cites it only to a PhD thesis. Maybe you can find a published proof.