2
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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 finding 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. $\endgroup$ May 24, 2012 at 3:48
  • $\begingroup$ 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). $\endgroup$ May 24, 2012 at 3:58
  • $\begingroup$ Well, since there's no response, I suppose there's a problem with my reduction to Ham cycle? $\endgroup$ May 30, 2012 at 2:02
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any copy saved on the Wayback Machine. $\endgroup$ Apr 18, 2023 at 14:41
  • $\begingroup$ Reposting a link mentioned in a previous comment so that it is clickable: arXiv:cs/0504038v5 [cs.CC]. The full citation should be: Manthey, Bodo, On approximating restricted cycle covers, SIAM J. Comput. 38, No. 1, 181-206 (2008). Zbl 1165.05028. $\endgroup$ May 6, 2023 at 10:28
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.