User some newbie - MathOverflow

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

2012-05-23T23:32:40Z

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.

Comment by Some Newbie

2012-05-30T02:02:20Z

Well, since there's no response, I suppose there's a problem with my reduction to Ham cycle?

Comment by Some Newbie

2012-05-24T03:58:48Z

A specific example of my problem would be: [br] (1) There are 100 locations with edges being the distances between them (2) You want to draw 11 disjoint cycles with lengths x1,x2,...,x11 where x1+x2+...+x11 = 100 and the overall distances are maximized. In the simplest case of this type of problem with only 1 cycle of length 100 then thats the maximum Hamiltonian cycle problem (which should be NP-hard, my memory serves).

Comment by Some Newbie

2012-05-24T03:48:54Z

Hmm, what's strange is that this paper here (arxiv.org/pdf/cs.cc/0504038.pdf) said:[br] 1. A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. (Yes, that applies) 2. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. (Yes, that applies) [br] 3. Hell et al. showed that ﬁnding L-cycle covers in undirected graphs is NP-hard for almost all L [br][br] Unfortunately, I can't read Hell et al's paper or the paper you linked me to, since I am no longer in school.