User some newbie - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T10:00:07Z http://mathoverflow.net/feeds/user/23913 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97800/need-input-on-a-potentially-np-hard-maximal-edge-weighted-multi-cycle-graph Need input on a potentially NP-hard maximal edge-weighted multi-cycle graph Some Newbie 2012-05-23T23:32:40Z 2012-05-24T01:24:55Z <p>I've posted a question on <a href="http://stackoverflow.com/questions/10567656/need-input-on-a-potentially-np-hard-maximal-edge-weighted-multi-cycle-graph">Stack Overflow</a> regarding a seemingly NP-hard problem on maximization of weighted cycles in a graph problem.</p> <p>One of the respondents cited <a href="http://mathoverflow.net/questions/24215/optimization-over-permutation" rel="nofollow">Professor David Speyer's Math Overflow post</a> 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?</p> <p>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.</p> http://mathoverflow.net/questions/97800/need-input-on-a-potentially-np-hard-maximal-edge-weighted-multi-cycle-graph/97806#97806 Comment by Some Newbie Some Newbie 2012-05-30T02:02:20Z 2012-05-30T02:02:20Z Well, since there's no response, I suppose there's a problem with my reduction to Ham cycle? http://mathoverflow.net/questions/97800/need-input-on-a-potentially-np-hard-maximal-edge-weighted-multi-cycle-graph/97806#97806 Comment by Some Newbie Some Newbie 2012-05-24T03:58:48Z 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). http://mathoverflow.net/questions/97800/need-input-on-a-potentially-np-hard-maximal-edge-weighted-multi-cycle-graph/97806#97806 Comment by Some Newbie Some Newbie 2012-05-24T03:48:54Z 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.