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.
 A: 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.
For directed graphs, or undirected graphs where edges are treated as cycles of length 2 (so their weight counts twice), it is easy to do it in polynomial time using a maximum matching algorithm. 
A: This is pretty late but I'm fairly sure that if the user is allowed to request that they want n cycles, Some Newbie is right that this problem is NP-Hard. The proof goes as follows:
Take some Hamiltonian cycle instance P. Embed it into our graph G for this problem by assigning all the weights of edges that don't occur in P to 0, and the edges that do occur to 1.
Now, ask for one cycle that has maximum weight. If the weight of this cycle equals |V|, we know that there is a Hamiltonian cycle, otherwise if it is less than |V|, we know there is not, thus this solves the Hamiltonian cycle decision problem, which is known to be NP-Complete.
It seems that if the user isn't allowed to specify the number of cycles, however, this gives enough flexibility that this problem is now solvable in poly time.
My suspicion is that this is where the confusion was.
